반응형

문제 출처 :


https://www.acmicpc.net/problem/11266



알고리즘 분석 :


문제 해결에 필요한 사항

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> vc[10002];
int discovered[10002];
bool isCut[10002];
 
int number;
 
// here == 정점 A
int dfs(int here, bool isRoot)
{
    discovered[here] = ++number; // DFS 탐색 순서 지정
    int ret = discovered[here];
 
    int child = 0; // 자식 수 count
 
    for (int i = 0; i < vc[here].size(); i++)
    {
        int next = vc[here][i];
 
        /* 
         만약 이미 DFS에서 탐색된 정점이라면 
         현재 정점의 방문순서와 탐색된 정점의 방문 순서중 min값을 찾는다.
         이 방법을 이용해야 
         " A번 정점에서 자식 노드들이 정점 A를 거치지 않고 
         정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다. "
         를 찾을 수 있다.
        */
        if (discovered[next])
        {
            ret = min(ret, discovered[next]);
            continue;
        }
 
        child++;
        int prev = dfs(next, false);
 
        /*
            정점 A가 루트가 아니라면 ::
            A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.
        */
        if (!isRoot && prev >= discovered[here])
            isCut[here] = true;
 
        ret = min(ret, prev);
    }
 
    /*
        정점 A가 루트 라면 ::
        자식 수가 2개 이상이면 단절점이다.
    */
    if (isRoot)
        isCut[here] = (child >= 2);
 
    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, true);
 
    int cnt = 0;
    for (int i = 1; i <= V; i++)
        if (isCut[i])
            cnt++;
 
    printf("%d\n", cnt);
    for (int i = 1; i <= V; i++)
        if (isCut[i])
            printf("%d ", i);
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1205번] 등수 구하기  (2) 2018.02.22
[11400번] 단절선  (0) 2018.02.22
[2792번] 보석 상자  (2) 2018.02.21
[10814번] 나이순 정렬  (0) 2018.02.20
[14927번] 전구 끄기  (0) 2018.02.19

티스토리툴바