moi dam cuoi code

 avatar
unknown
plain_text
2 years ago
1.2 kB
1
Indexable
#include<iostream>

using namespace std;

int N, M, u, v;
int matrix[105][105];

int visit[105];
int cntTime[105];

int cntRoad;

void init() {
	cntRoad = 0;

	for (int i = 1; i <= N; i++)
		visit[i] = cntTime[i] = 0;
}

void reset() {
	for (int i = 1; i <= N; i++)
		for (int j = i; j <= N; j++)
			matrix[i][j] = matrix[j][i] = 0;
}

void DFS(int start, int end) {
	if (start == end) {
		cntRoad++;

		for (int i = 1; i <= N; i++)
			if (visit[i])
				cntTime[i]++;

		return;
	}

	for (int i = 1; i <= N; i++) {
		if (matrix[start][i] && !visit[i]) {
			visit[i] = 1;
			DFS(i, end);
			visit[i] = 0;
		}
	}
}

int main() {
	int T;
	//freopen("sample_input.txt", "r", stdin);
	cin >> T;

	for(int test_case = 1; test_case <= T; ++test_case) {
		cin >> N >> M >> u >> v;

		init();
		reset();

		int i, j;
		for (int m = 0; m < M; m++) {
			cin >> i >> j;
			matrix[i][j] = 1;
		}

		visit[u] = 1;
		DFS(u, v);
		visit[u] = 0;

		int ans = 0;

		for (int i = 1; i <= N; i++)
			if (i != u && i != v && cntTime[i] == cntRoad)
				ans++;


		cout << ans << endl << endl;
	}
	return 0;
}
Editor is loading...