# 1. dfs 부분을 visit 배열로 했을 경우
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <stdio.h> #include <string.h> int fin[100005]; int arr[100005]; int visit[100005]; int start, cnt = 0; void dfs(int idx); int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); memset(fin, 0, sizeof(int) * (n + 1)); memset(arr, 0, sizeof(int) * (n + 1)); memset(visit, 0, sizeof(int) * (n + 1)); for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } cnt = 0; for (int i = 1; i <= n; i++) { if (visit[i] == 0) { dfs(i); } } printf("%d\n", cnt); } } void dfs(int idx) { if (visit[idx] == 0) { visit[idx] = 1; dfs(arr[idx]); } else if (visit[idx] == 1 && fin[idx] == 0) { cnt++; } fin[idx] = 1; } | cs |
# 2. dfs 부분을 fin 으로 처리했을 경우
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <stdio.h> #include <string.h> int fin[100005]; int arr[100005]; int visit[100005]; int start, cnt = 0; void dfs(int idx); int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); memset(fin, 0, sizeof(int) * (n + 1)); memset(arr, 0, sizeof(int) * (n + 1)); memset(visit, 0, sizeof(int) * (n + 1)); for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } cnt = 0; for (int i = 1; i <= n; i++) { if (fin[i] == 0) { dfs(i); } } printf("%d\n", cnt); } } void dfs(int idx) { if (visit[idx] == 0) { visit[idx] = 1; dfs(arr[idx]); } else if (visit[idx] == 1 && fin[idx] == 0) { cnt++; } fin[idx] = 1; } | cs |
'알고리즘 > DFS' 카테고리의 다른 글
11438 LCA2 (0) | 2019.09.15 |
---|---|
11437 LCA (0) | 2019.09.14 |
9466 텀 프로젝트(hard) (0) | 2019.09.03 |
2668 숫자 고르기 (0) | 2019.09.03 |
1991 트리 순회 (0) | 2019.08.26 |