단절점 / 단절선

[WonYong-Jang]

단절점

하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트(그래프)로 나누어지는 정점을 단절점

단절점 특징

• 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지 않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단 가능
  즉, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않다!

• 비효율적인 방법 : 모든 정점을 한번씩 선택(V) 하여 제거한 후 그래프가 나뉘어지는지 파악 ( V * E)
  ==> 시간복잡도 O( V * ( V + E))

• DFS 스패닝 트리를 이용하여 단절점을 빠른시간내에 구할수 있음

구현 방법

• dfs 를 이용하여 정점들의 방문 순서를 기록
• 특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈수 없다면 단절점이다.

예외 케이스

• 루트노드로 잡은 특정 노드의 자식 수가 2개 이상이면 무조건 단절점이다!

정점 A가 루트라면
==> 자식 수가 2개 이상이면 단절짐이다.
정점 A가 루트가 아니라면
==> A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점

==>한번의 dfs 로 답을 구할수 있기 때문에 O(N + M) 

public class baek11266 {

	static int V, E, number;
	static boolean[] cut = new boolean[10005]; // 단절점 여부 확인 배열 ! 
	static int[] order = new int[10005]; // 방문 순서 기록 !! 
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException {
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		number =0; // 방문 순서 기록 할 숫자 

		for(int i=1; i<= V; i++)
		{
			if(order[i] > 0) continue;
			dfs(i, 0);
		}
		
		int cnt =0;
		for(int i=1; i<= V; i++)
		{
			if(cut[i]) cnt++;
		}
		bw.write(cnt+"\n");
		for(int i=1; i<= V; i++)
		{
			if(cut[i]) 
			{
				bw.write(i+" ");
			}
		}
		bw.flush();
	}
	public static int dfs(int cur, int p)
	{
		order[cur] = ++number; // 방문순서 지정 
		int ret = order[cur];
		int child = 0; // root 자식 수가 2개 확인하기 위함 
		for(int next : adj.get(cur))
		{
                         if( next == p ) continue;
			if(order[next] > 0) // 이미 방문한 지점이라면 가장 작은 순서 찾아서 업데이트 
			{
				ret = min(ret, order[next]);
				continue;
			}
			
			child++;
			
			int prev = dfs(next, cur);
			
			if(p != 0 && prev >= order[cur]) {
				cut[cur] = true; // 단절점 
			}
			ret = min(ret, prev);
		}
		
		if(p ==0 && child >= 2) cut[cur] = true;
		
		return ret;
	}
}

단절선

public class Main {

	static int N, K, number;
	static int[] order = new int[100005];
	static ArrayList<Node> result = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException {
		
		for(int i=1; i<= N; i++)
		{
			if(order[i] > 0) continue;
			dfs(i, 0);
		}
	}
	public static int dfs(int cur, int p)
	{
		order[cur] = ++number;
		int ret = order[cur];
		
		for(int next : adj.get(cur))
		{
			if(next == p) continue;
			
			if(order[next] > 0)
			{
				ret = min(ret, order[next]);
				continue;
			}
			
			int prev = dfs(next, cur);
			
			if(prev > order[cur])
			{
				result.add(new Node(min(cur, next), max(cur, next)));
			}
			
			ret = min(prev, ret);
		}
		
		return ret;
	}
}

트리 에서의 단절점과 단절선 !! ( 사이클이 없는 ) / 주의!!

트리에서는 사이클이 존재하지 않기 때문에 단절선이 아닌 선은 없다!

단절점 같은 경우는 연결된 간선이 2개 이상이면 단절점 이다.

백준 14675 단절점과 단절선 문제

출처 : https://www.crocus.co.kr/1164