Untitled

 avatar
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