단절점
하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거 했을 때 그래프가 두개 이상의 컴포넌트(그래프)로 나누어지는 정점을 단절점이라고 합니다.
단절점 특징
어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지 않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단 가능합니다.
즉, 단절점에 바로 인접해 있는 장점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않다!!
비효율적인 방법 : 모든 정점을 한번씩 선택하여 제거한 후 그래프가 나뉘어지는지 파악 ( V * E ) => 시간복잡도 O(V * ( V + E ))
DFS 스패닝 트리를 이용한 시간 복잡도는 O(N + M) 입니다.
구현 방법
1. DFS 를 이용하여 정점들의 방문 순서를 기록합니다
2. 특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문 번호를 가진 정점으로 갈수 없다면 단절점입니다.
특정 A번 정점에서 자식노드들 중 하나라도 정점 A번보다 빠른 방문 번호를 리턴하지 않으면 두개로 분리된 트리가 나온다는 의미이므로 단절점으로 판단합니다!
예외 케이스
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
public class Main {
static int N, M, number;
static ArrayList<Integer>[] adj = new ArrayList[100001];
static int[] order = new int[10001]; // 순서 배열
static boolean[] cut = new boolean[10001]; // 단절점 체크
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
number = 0;
for(int i=1; i<= N; i++)
{
adj[i] = new ArrayList<>();
}
int dx = 0, dy = 0;
for(int i=1; i<= M; i++)
{
st = new StringTokenizer(br.readLine());
dx = Integer.parseInt(st.nextToken());
dy = Integer.parseInt(st.nextToken());
adj[dx].add(dy);
adj[dy].add(dx);
}
for(int i=1; i<= N; i++)
{
if(order[i] > 0) continue; // 방문 기록있으면 continue
search(0, i); // root를 0 으로 표시
}
int cnt = 0;
StringBuilder sb = new StringBuilder();
for(int i=1; i<= N; i++)
{
if(cut[i]) {
cnt++;
sb.append(i+" ");
}
}
bw.write(cnt+"\n");
bw.write(sb.toString()+"\n");
bw.flush();
}
public static int search(int p, int cur)
{
order[cur] = ++number; // 순서 표시
int ret = order[cur]; // 가장 빠른 순서 체크
int child = 0; // 자식 수
for(int next : adj[cur])
{
if(next == p) continue; // 부모면 continue
if(order[next] > 0 )
{
ret = Math.min(ret, order[next]);
continue;
}
child++;
int prev = search(cur, next);
if(p != 0 && prev >= order[cur]) // root 가 아니고 자식이 더 빠른 방문순서로 갈수 없다면 단절
{
cut[cur] = true;
}
ret = Math.min(ret, prev);
}
if(p == 0 && child >= 2) cut[cur] = true;
return ret;
}
}