[백준]20530. 양분

📄 링크

양분

---

💡 문제 분석

이런 문제가 왜 골드2인지 모를 정도로 힘든 문제였습니다.
처음엔 아무 생각 없이 dfs로 모든 경로를 다 찾아보려 했지만 정점이 200000개.. 당연히 시간초과가 떴습니다

이 문제의 핵심은 간선의 개수가 정점의 개수와 같기 때문에 반드시 하나의 사이클이 존재한다는 것입니다.

예제 입력을 그래프로 그려보았습니다.
어떤 두 정점으로 가는 단순 경로는 사이클이 하나이기 때문에 2개 또는 1개 밖에 나올 수 없습니다

2가지가 나오는 경우

1. 두 정점이 모두 사이클에 속해 있는 경우 양 방향으로 갈 수 있기 때문에 2가지 경로가 존재합니다
2. LCA(최소 공통 조상)이 다른 경우

• 사이클을 구성하고 있는 정점들을 루트로 아래쪽 부분을 서브트리라고 생각했을 때 다른 루트에서 뻗어나왔다면 사이클을 경유해서 갈 수 있기 때문에 2가지 경로가 존재합니다.

1가지가 나오는 경우

• 그 이외 최소 공통 조상이 같은 경우 사이클을 경유하지 않기 때문에 1가지 경로 밖에 존재하지 않습니다

그렇다면 구현해야 하는 것은

1. 그래프에서 사이클을 찾고 거기에 포함되어 있는 정점들을 뽑아내기
2. 사이클을 구성하는 정점들을 루트로 bfs를 통하여 서브 트리 노드들을 최소 공통 조상 별로 분리하기

2가지가 되겠습니다.

• 자바에서는 이렇게 하고도 시간 초과가 발생해서 BufferedReader와 StringBuilder 출력을 하고 나서야 통과할 수 있었습니다.

---

⌨️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class _20530_양분 {

    static int N, Q;
    static boolean[] visited, finished, isCycle;
    static int[] parent, ancestor;
    static ArrayList<Integer>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        adj = new ArrayList[N + 1];
        parent = new int[N + 1];
        ancestor = new int[N + 1];
        finished = new boolean[N + 1];
        isCycle = new boolean[N + 1];
        visited = new boolean[N + 1];
        for(int i = 0; i < N + 1; i++)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            adj[from].add(to);
            adj[to].add(from);
        }
        dfs(1, 0);
        Arrays.fill(visited, false);
        for(int i = 1; i < N + 1; i++) {
           if(isCycle[i] && !visited[i]) {
               bfs(i);
           }
        }

        for(int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            if(isCycle[u] && isCycle[v])
                sb.append("2\n");
            else if(ancestor[u] != ancestor[v])
                sb.append("2\n");
            else
                sb.append("1\n");
        }
        System.out.println(sb);
    }

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        while(!q.isEmpty()) {
            int cur = q.poll();
            visited[cur] = true;
            ancestor[cur] = start;

            for(int next : adj[cur]) {
                if(isCycle[next] || visited[next]) continue;
                q.add(next);
            }
        }
    }

    public static void dfs(int cur, int before) {
        visited[cur] = true;
        for(int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur].get(i);
            if(!visited[next]) {
                parent[next] = cur;
                dfs(next, cur);
            }
            else if(!finished[next] && next != before) {
                denoteCycle(cur, next);
            }
        }
        finished[cur] = true;
    }

    public static void denoteCycle(int cur, int next) {
        isCycle[cur] = true;
        if(cur == next) return;
        denoteCycle(parent[cur], next);
    }
}

---

📋 회고

• 그래프에서 사이클 뽑아내기
• 시간 맞추기 너무 어려워