[BOJ 20955, Python 3] 민서의 응급 수술

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

20955번: 민서의 응급 수술

 

 

풀이

일단 연결되지 않은 두 뉴런을 연결할 때를 생각해보면 트리와 트리를 연결할 때만 필요하다는 것을 알 수 있습니다. 우선 이 값은 (트리의 수) - 1로 결정됩니다.

 

이미 연결된 두 뉴런을 끊을 때를 생각해보면 하나의 연결 요소를 트리로 만들 때만 사용한다는 것을 알 수 있습니다. 이건 bfs나 dfs를 이용해서 사용하는 간선을 구해주면 됩니다.

이러면 (해당 연결 요소의 간선의 개수) - (사용하는 간선의 개수)만큼만 끊어주면 트리가 됩니다.

연결 요소가 여러 개이므로 (전체 간선의 개수) - (사용하는 간선의 개수)

 

그래서 코드는 연결 요소의 개수를 구하면서 1번 정점부터 확인하여 bfs를 통해 사용하는 간선의 개수를 구해주고, bfs가 전부 끝난다면 (트리의 수 - 1) + (전체 간선의 개수 - 사용하는 간선의 개수)를 출력해주면 됩니다.

 

 

 

코드

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
visit = [0] * (n + 1)
for i in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
ans = -1
edge = 0
for i in range(1, n+1):
    if not visit[i]:
        ans += 1
        visit[i] = 1
        q = __import__('collections').deque([i])
        while q:
            x = q.popleft()
            for nx in adj[x]:
                if not visit[nx]:
                    visit[nx] = 1
                    q.append(nx)
                    edge += 1
print(ans + m - edge)