반응형
문제 출처 :
https://www.acmicpc.net/problem/1325
알고리즘 분석 :
문제 해결에 필요한 사항
1. 단방향 그래프
2. dfs
이 문제는 a->b가 신뢰한다면 결국 b->a로 해킹 할 수 있다는 것이다.
따라서 예제 입력인
3 1
3 2
4 3
5 3
를 본다면 아래와 같은 단방향 그래프가 형성되는 것이다.
결국 자신으로부터 종속된 노드가 몇개가 있는지 찾는 것이고(이 과정을 해킹이라고 말하고 있다.)
가장 많이 종속하고 있는(여러개가 될 수 도 있다.(여기선 1,2가 답)) 노드를 출력하는 것이다.
따라서 dfs를 통해 자신의 노드의 개수를 구하면 되는 문제.
아래 코드는 실질적으로 자신을 포함한 노드 개수가 나타나는데
cnt[i] = dfs(i) - 1;로 고쳐주면 온전한 자식 노드의 개수만 구할 수 있다.
소스 코드 :
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <iostream> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <memory.h> using namespace std; vector<int> vc[10001]; bool visit[10001]; int tmp[10001]; int cnt[10001]; vector<int> ans; // 자신을 포함한 자식 노드 전체 개수 구하는 알고리즘 int dfs(int start) { if (visit[start] == true) return 0; visit[start] = true; for (int i = 0; i < vc[start].size(); i++) { int there = vc[start][i]; tmp[start] += dfs(there); } return tmp[start] + 1; } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int from, to; scanf("%d %d", &from, &to); vc[to].push_back(from); } for (int i = 1; i <= n; i++) { memset(visit, false, sizeof(visit)); memset(tmp, 0, sizeof(tmp)); cnt[i] = dfs(i); } // 정렬 알고리즘 int MAX = cnt[1]; ans.push_back(1); for (int i = 2; i <= n; i++) { if (cnt[i] > MAX) { ans.clear(); MAX = cnt[i]; ans.push_back(i); } else if (cnt[i] == MAX) ans.push_back(i); } sort(ans.begin(), ans.end()); int len = ans.size(); for (int i = 0; i < len; i++) printf("%d ", ans[i]); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[2225번] 합분해 (0) | 2017.03.20 |
---|---|
[10942번] 팰린드롬? (0) | 2017.03.19 |
[10825번] 국영수 (0) | 2017.03.18 |
[1365번] 꼬인 전깃줄 (0) | 2017.03.17 |
[3176번] 도로 네트워크 (0) | 2017.03.17 |