[파이썬,자바] 백준 13232 : Domain clusters (플레5)

[파이썬,자바] 백준 13232 : Domain clusters (플레5)

• https://www.acmicpc.net/problem/13232

---

풀이

방향성 생각

• SCC의 컴포넌트 중 가장 사이즈가 큰 scc의 사이즈를 출력하면 된다.
• 타잔이나 코사라주 아무거나 써서 scc 컴포넌트 구하고 크기 출력하기.

 

---

전체코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)

input = lambda : sys.stdin.readline().strip()

N = int(input())
M = int(input())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)


V = [-1]*(N+1)
P = [-1]*(N+1)
counter = [0]
stack = deque()
on_stack = [False]*(N+1)

SCC = []
def dfs(x):

    V[x] = counter[0]
    P[x] = counter[0]
    counter[0] += 1
    stack.append(x)
    on_stack[x] = True

    for nx in G[x]:
        if V[nx] == -1:
            dfs(nx)
            P[x] = min(P[x],P[nx])
        elif on_stack[nx]:
            P[x] = min(P[x],V[nx])

    if V[x] == P[x]:
        scc = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            scc.append(w)
            if w==x:
                break
        SCC.append(scc)

for x in range(N):
    if V[x]==-1:
        dfs(x)

print(len(max(SCC,key=lambda scc:len(scc))))

import java.io.*;
import java.util.*;

public class Main {

    static int N, M;
    static ArrayList<ArrayList<Integer>> G, SCC;
    static int[] V, P;
    static int[] counter;
    static ArrayDeque<Integer> stack;
    static boolean[] onStack;

    static void dfs(int x) {
        V[x] = counter[0];
        P[x] = counter[0];
        counter[0]++;
        stack.push(x);
        onStack[x] = true;

        for (int nx : G.get(x)) {
            if (V[nx] == -1) {
                dfs(nx);
                P[x] = Math.min(P[x], P[nx]);
            } else if (onStack[nx]) {
                P[x] = Math.min(P[x], V[nx]);
            }
        }

        if (P[x] == V[x]) {
            ArrayList<Integer> scc = new ArrayList<>();
            while (true) {
                int w = stack.pop();
                onStack[w] = false;
                scc.add(w);
                if (w == x) break;
            }
            SCC.add(scc);
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        G = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            G.add(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());
            G.get(a).add(b);
        }

        V = new int[N + 1];
        Arrays.fill(V, -1);
        P = new int[N + 1];
        Arrays.fill(P, -1);
        counter = new int[1];
        stack = new ArrayDeque<>();
        onStack = new boolean[N + 1];
        SCC = new ArrayList<>();

        for (int x = 1; x <= N; x++) {
            if (V[x] == -1) {
                dfs(x);
            }
        }

        int answer = 0;
        for (ArrayList<Integer> scc : SCC) {
            answer = Math.max(answer, scc.size());
        }
        System.out.println(answer);
    }
}

코멘트

• .