moi dam cuoi code
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...