반응형
https://www.acmicpc.net/problem/11266
11266번: 단절점
첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!
https://rudalsd.tistory.com/113?category=1064608
[ 알고리즘 ] 단절점(Articulation Point)
1. 단절점(Articulation Point)이란? 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정
rudalsd.tistory.com
[ 소스코드 ]
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 | #include<iostream> #include<vector> using namespace std; int V, E; vector<int> list[10001]; int id[10001]; int ans[10001]; int cur = 1; int dfs(int node, bool root) { id[node] = cur++; int ret = id[node]; int child = 0; for (auto next : list[node]) { if (id[next]) { //이미 방문했다면 ret = min(ret, id[next]); continue; } child++; //자식의 개수 int minId = dfs(next, false); //갈수 있는 노드 중 가장 id값이 낮은 노드 if (!root && minId >= id[node]) { //루트가 아니고 자신보다 더 낮은 id값을 가진 노드로 가지 못할 때 ans[node] = 1; } ret = min(ret, minId); } if (root && child > 1) { ans[node] = 1; } return ret; } int main() { scanf("%d %d", &V, &E); for (int i = 0; i < E; i++) { //그래프 만들기 int a, b; scanf("%d %d", &a, &b); list[a].push_back(b); list[b].push_back(a); } for (int i = 1; i <= V; i++) { //방문하지 않은 노드라면 if (!id[i]) { dfs(i, true); } } int cnt = 0; for (int i = 1; i <= V; i++) { //단절점의 개수 if (ans[i] == 1) cnt++; } printf("%d\n", cnt); for (int i = 1; i <= V; i++) { //단절점 출력 if (ans[i] == 1) printf("%d ", i); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2178번 - 미로 탐색 (C++) (0) | 2022.08.30 |
|---|---|
| [ 백준 ] 11400번 - 단절선 (C++) (0) | 2022.08.29 |
| [ 백준 ] 3653번 - 영화 수집 (C++) (0) | 2022.08.25 |
| [ 백준 ] 1153번 - 길의 개수 (C++) (0) | 2022.08.24 |
| [ 백준 ] 11286번 - 절댓값 힙 (C++) (0) | 2022.08.23 |