[BOJ 6672] Electricity

문제

---

https://www.acmicpc.net/problem/6672

풀이

---

BCC를 구현하고 푼 첫 문제이다.

추가로 각 노드 별로 속해있는 BCC의 개수를 구해, 그중 제일 큰 값을 가지는 노드를 제거하면 정답이 된다.

코드

---

import sys
sys.setrecursionlimit(10 ** 4)


def dfs(cur, parent):
    global idx
    dfsn[cur] = idx
    low = idx
    idx += 1

    for nxt in graph[cur]:
        if nxt == parent:
            continue

        if not dfsn[nxt]:
            stack.append((cur, nxt))
            child = dfs(nxt, cur)
            low = min(low, child)

            if dfsn[cur] <= child:
                adj[cur] += 1
                res = []
                while stack[-1] != (cur, nxt):
                    res.append(stack.pop())
                res.append(stack.pop())
                bcc.append(res)
            
        elif low > dfsn[nxt]:
            low = min(low, dfsn[nxt])
            stack.append((cur, nxt))
        
    return low


while True:
    n, m = map(int, sys.stdin.readline().split())
    if (n, m) == (0, 0):
        break

    graph = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    bcc = []
    stack = []
    dfsn = [0] * n
    adj = [1] * n
    idx = 1
    ans = 0

    for i in range(n):
        if not dfsn[i]:
            dfs(i, -1)
            adj[i] -= 1
            ans += 1

    print(ans + max(adj) - 1)