Dot Algo∙ DS/PS

[알고리즘] 단절선 (백준 11400번 풀이)

루지 2022. 3. 2. 12:43

    #11400 단절선

    난이도 : 플레 5

    유형 : 그래프 / 단절선 / DFS

     

    11400번: 단절선

    첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A

    www.acmicpc.net

    ▸ 문제

    그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

    단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

     입력

    첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

    그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

    그래프의 정점은 1부터 V까지 자연수이다.

     출력

    첫째 줄에 단절선의 개수 K를 출력한다.

    둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

     

    문제 풀이  

    DFS 응용 알고리즘인 단절점과 단절선의 문제이다. 어떤 간선을 지웠을 때 해당 컴포넌트가 2개 이상으로 나뉘어지는 간선을 찾으면 된다. 단절선은 루트나 어떤 조건을 신경쓰지 않고 단순히 단절점 + 단절점의 부모노드를 연결지어주면 되기 때문에 그냥 역방향 간선만 잡아주면 된다.

     

    단절선 찾기

    DFS 탐색을 수행하면 다음과 같이 스패닝 트리를 만들 수 있다. 무향 그래프에서는 교차 간선이 없으므로, u와 연결된 정점은 선조아니면 자손이다.

    • 이때 u의 자손들을 루트로 하는 서브트리들은 서로 연결되어 있지 않다. 그 간선들은 교차간선이어야 하는데 위에서 말했다시피 양방향 그래프에서는 교차 간선이 존재할 수 없기 때문이다. 따라서 그냥 하나의 서브트리로 구분된다.
    • u가 지워졌을 때 그래프가 쪼개지지 않는 유일한 경우는 그림과 같이 역방향 간선으로 연결되어 있을 때 뿐이라고 볼 수 있다.
    • 따라서 단절선은 u와 u의 부모노드를 연결해주는 간선이다.

    단절선 찾기

     

    마지막으로 모든 단절선을 구했으면 오름차순으로 잘 정렬해서 출력해주면 된다.

     

    단절점 풀이 방법은 여기를 참고해주세요

     

    풀이 코드 

    import java.io.*;
    import java.util.*;
    
    public class Main {
    
    	static List<Integer>[] list;
    	static List<int[]> cutVtx;
    	static int[] discovered;
    	static int counter;
    	public static void main(String[] args) throws IOException{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		
    		int v = Integer.parseInt(st.nextToken());
    		int e = Integer.parseInt(st.nextToken());
    		
    		
    		cutVtx = new ArrayList<>();
    		discovered = new int[v+1];
    		list = new ArrayList[v+1];
    		for(int i=0; i<=v; i++) {
    			list[i] = new ArrayList<>();
    			discovered[i] = -1;
    		}
    		
    		for(int i=0; i<e; i++) {
    			st = new StringTokenizer(br.readLine());
    			int a = Integer.parseInt(st.nextToken());
    			int b = Integer.parseInt(st.nextToken());
    			
    			list[a].add(b);
    			list[b].add(a);
    		}
    		
    		
    		for(int i=1; i<=v; i++) {
    			if(discovered[i] == -1) {
    				findCutVertex(i, 0);
    			}
    		}
    		
    		Collections.sort(cutVtx, (a,b) -> (a[0] == b[0]) ? a[1]-b[1] : a[0]-b[0]);
    		StringBuilder sb = new StringBuilder();
    		int cnt = cutVtx.size();
    		for(int i=0; i<cutVtx.size(); i++) {
    			sb.append(cutVtx.get(i)[0]+" "+cutVtx.get(i)[1]);
    			sb.append("\n");
    		}
    		
    		System.out.println(cnt);
    		if(cnt > 0) {
    			System.out.println(sb.toString());	
    		}
    	}
    	
    	static int findCutVertex(int cur, int root) {
    		discovered[cur] = counter++;
    		int ret = discovered[cur];
    		for(int i=0; i<list[cur].size(); i++) {
    			int nxt = list[cur].get(i);
    			if(nxt == root) continue;
    			if(discovered[nxt] == -1) {
    				// 해당 서브트리에서 갈 수 있는 가장 먼저 발견된 정점 번호
    				int subTree = findCutVertex(nxt, cur);
    				
    				// 그 노드(subTree)가 자기 자신 이하에 있다면 단절점 u(nxt)찾음
    				if(subTree > discovered[cur]) {
    					// 단절선은 nxt와 해당 부모노드 cur로 연결된 간선
    					cutVtx.add(new int[] {Math.min(cur, nxt), Math.max(cur, nxt)});
    				}
    				ret  = Math.min(ret, subTree); // 가장 먼저 발견된 정점 찾기
    			}else {
    				ret  = Math.min(ret, discovered[nxt]); // 가장 먼저 발견된 정점 찾기
    			}
    		}
    		
    		return ret;
    	}
    }