Untitled
unknown
plain_text
2 years ago
1.7 kB
6
Indexable
#include <iostream> using namespace std; int T, M, N, u, v; int cnt[101]; int arr[101][101]; int map[101][101]; int visited[101]; int ans; bool check; class Queue{ int front, rear; int q[10000]; public: Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } void Queue::reset(){ front = rear = -1; } bool Queue::is_Empty(){ return front == rear; } Queue mQueue; int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M >> u >> v; int x, y; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ arr[i][j] = 0; map[i][j] = 0; } } for(int i = 0; i < M; i++){ cin >> x >> y; arr[x][y] = 1; } ans = 0; for(int i = 1; i <= N; i++){ if(i != u && i != v){ for(int j = 1; j <= N; j++){ for(int k = 1; k <= N; k++){ map[j][k] = arr[j][k]; } } for(int j = 1; j <= N; j++){ map[j][i] = 0; visited[j] = 0; } mQueue.reset(); visited[u] = 1; mQueue.enQueue(u); check = false; while(mQueue.is_Empty() == false){ int tmp = mQueue.deQueue(); for(int i = 1; i <= N; i++){ if(map[tmp][i] == 1 && visited[i] == 0){ visited[i] = 1; mQueue.enQueue(i); if(i == v){ check = true; goto next; } } } } next: if(check == false) ans++; } } cout << ans << endl << endl; } return 0; }
Editor is loading...
Leave a Comment