반응형
문제 출처 :
https://www.acmicpc.net/problem/11400
알고리즘 분석 :
문제 해결에 필요한 사항
1. 단절선
단절선에 대해 이해하고 있다면 쉽게 문제를 해결 할 수 있다.
이 문제는 단절선 기본 개념을 묻는 문제이므로 아래 링크를 참조해보자.
http://www.crocus.co.kr/1164?category=209527
소스 코드 :
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 | #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> vc[100002]; int discovered[100002]; vector<pair<int, int> > isCut; int number; // here == 정점 A int dfs(int here, int parent) { discovered[here] = ++number; // DFS 탐색 순서 지정 int ret = discovered[here]; for (int i = 0; i < vc[here].size(); i++) { int next = vc[here][i]; if (next == parent) continue; if (discovered[next]) { ret = min(ret, discovered[next]); continue; } int prev = dfs(next, here); if (prev > discovered[here]) isCut.push_back({ min(here, next), max(here, next) }); ret = min(ret, prev); } return ret; } int main() { int V, E; scanf("%d %d", &V, &E); for (int i = 0; i < E; i++) { int from, to; scanf("%d %d", &from, &to); vc[from].push_back(to); vc[to].push_back(from); } for (int i = 1; i <= V; i++) if (!discovered[i]) dfs(i, 0); sort(isCut.begin(), isCut.end()); printf("%d\n", isCut.size()); for (int i = 0; i < isCut.size(); i++) printf("%d %d\n", isCut[i].first, isCut[i].second); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[11811번] 데스스타 (0) | 2018.02.22 |
---|---|
[1205번] 등수 구하기 (2) | 2018.02.22 |
[11266번] 단절점 (0) | 2018.02.21 |
[2792번] 보석 상자 (2) | 2018.02.21 |
[10814번] 나이순 정렬 (0) | 2018.02.20 |