moi dam cuoi code
unknown
plain_text
2 years ago
1.2 kB
4
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...