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 49 50 51 52 53 54 55 56 | #include <stdio.h> #include <vector> #include <string.h> using namespace std; vector<vector<int> > adj; int from[1005] = { 0 }; int visit[1005] = { 0 }; int dfs(int idx); int main() { int n, m; scanf("%d %d", &n, &m); adj.resize(n + 1); for (int i = 1; i <= n; i++) { int num; scanf("%d", &num); while (num--) { int k; scanf("%d", &k); adj[i].push_back(k); } } int cnt = 0; for (int i = 1; i <= n; i++) { memset(visit, 0, sizeof(visit)); if (dfs(i)) cnt++; } printf("%d", cnt); } int dfs(int idx) { if (visit[idx] != 0) return 0; else visit[idx] = 1; for (int i = 0; i < adj[idx].size(); i++) { int v = adj[idx][i]; int f = from[v]; if (from[v] == 0 || dfs(f) == 1) { from[v] = idx; return 1; } } return 0; } | cs |
(살짝 다른 풀이)
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <stdio.h> #include <vector> #include <string.h> using namespace std; vector<vector<int> > adj; int from[1005] = { 0 }; int visit[1005] = { 0 }; int cnt = 0; int dfs(int idx); int main() { int n, m; scanf("%d %d", &n, &m); adj.resize(n + 1); for (int i = 1; i <= n; i++) { int num; scanf("%d", &num); while (num--) { int k; scanf("%d", &k); adj[i].push_back(k); } } for (int i = 1; i <= n; i++) { memset(visit, 0, sizeof(visit)); dfs(i); } int cnt = 0; for (int i = 1; i <= m; i++) { if (from[i] != 0) cnt++; } printf("%d",cnt); } int dfs(int idx) { if (visit[idx] != 0) return 0; else visit[idx] = 1; for (int i = 0; i < adj[idx].size(); i++) { int v = adj[idx][i]; int f = from[v]; if (from[v] == 0 || dfs(f) == 1) { from[v] = idx; return 1; } } return 0; } | cs |
'알고리즘 > DFS' 카테고리의 다른 글
| 6086 최대 유량 (0) | 2019.08.22 |
|---|---|
| 11376 열혈강호2 (0) | 2019.08.20 |
| 1987 알파벳 (0) | 2019.08.01 |
| 1389 케빈 베이컨의 6단계 법칙 (0) | 2019.08.01 |
| 6603 로또 (0) | 2019.07.31 |