<Algorithm> 64. 11400번 단절선

1. 11400번 단절선

• DFS Spanning Tree 문제, 단절점과 같이 풀어야 정확한 이해가 가능 할 듯 하다.

• 단절점과의 차이점은 온길을 제외하는 것과 자신을 비교대상에서 빼는 것 이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int count = 1;
    static int[] discovered;
    static ArrayList<Pair> ans = new ArrayList<Pair>();    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Node>[] aLists = new ArrayList[N];
        discovered = new int[N];
        
        for(int i = 0; i < N; i ++) {
            aLists[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            aLists[a].add(new Node(b));
            aLists[b].add(new Node(a));
        }
        
        for(int i = 1; i < N; i++)
            if(discovered[i] == 0) {
                dfs(i, 0, aLists);                
            }
        
        Collections.sort(ans,new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if(o1.x == o2.x)
                    return o1.y-o2.y; // 같을 경우 처리 반드시
                return o1.x - o2.x;
            }
        });
        
        System.out.println(ans.size());
        for(Pair par : ans) {
            System.out.println(par.x+" "+par.y);
        }
        
        
    }
    
    public static int dfs(int vertax, int parent,ArrayList<Node>[] aLists) {
        discovered[vertax] = count++;
        int ret = discovered[vertax];
        
        /*온 길을 제외하고 다른 길로 방문정점보다 앞 순서에 방문한 정점으로 갈 수 있으면 단절선이 아님 */
        
        for(Node node : aLists[vertax]) {
            
            if(node.adjVertax == parent) continue;
            
            if(discovered[node.adjVertax] == 0) {
                
                int low = dfs(node.adjVertax, vertax, aLists);
                
                if(low > discovered[vertax]) {
                    ans.add(new Pair(Math.min(vertax, node.adjVertax),Math.max(vertax, node.adjVertax)));
                }
                
                ret = Math.min(ret, low);
                
            }else {
                ret = Math.min(ret, discovered[node.adjVertax]);
            }
        }
        
        return ret;
    }
}
 
class Node{
    int adjVertax;
    public Node(int adjVertax) {
        super();
        this.adjVertax = adjVertax;
    }
}
 
class Pair{
    int x,y;
 
    public Pair(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}
 

출처 : http://bowbowbow.tistory.com/3, http://jason9319.tistory.com/119