ABC 350 D번 복기 - 직접 연결되어있지는 않지만 도달할 수 있는 경로의 개수 구하는법

D - New Friends (atcoder.jp)

D - New Friends

 

 

문제를 요약하자면...

 

어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면

 

그러한 경로의 개수를 구하는 문제

 

 

 

예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데,

 

1 > 2 > 3으로 갈 수 있으므로 1개

 

2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지 않으므로 

 

2 > 1 > 4로 도달할 수 있으니 1개

 

3번 노드에서 2번 노드는 직접 연결되어 있고, 1번 노드는 앞에서 도달할 수 있음을 보였고,

 

3 > 2 > 1 > 4로 도달할 수 있으니 1개

 

그래서 총 3개이다.

 

BFS로 도달할 수 있는 경로를 찾으면 될 것 같은데

 

n이 20만이라 BFS를 여러번 수행하는 순간  시간초과날 것 같고

 

BFS를 수행할려고 해도, 직접 연결된 노드와 직접 연결되지 않은 노드를 분리하는데만 해도 $O(N^{2})$이다보니...

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

생각을 바꿔서..

 

"이론적으로 존재해야하는 직접 연결하는 간선의 개수 - 실제 존재하는 간선의 개수 = 직접 연결되지 않았지만 도달 가능한 경로의 개수"

 

예를 들어 이 그래프는 1,2,3,4끼리 서로 도달가능하다.

 

 

 

따라서 이 그룹 내에 직접 연결된 간선의 개수는.. 4C2 = 6개

 

실제 존재하는 간선의 개수는 검정색 3개

 

문제에서 요구하는, 직접 연결되지 않았지만, 도달 가능한 경로의 개수인 빨간색 간선의 개수는 3개

 

이는 실제로 전체 6개 - 검정색 3개 = 빨간색 3개

 

 

 

 

 

그래서 전략을 바꿔서 주어진 그래프에서 서로 도달 가능한 그룹을 찾으면서 해당 그룹 내에 존재하는 노드 수를 찾고,

 

실제 존재하는 간선의 개수를 이용해서, 둘의 차이로 구하자.

 

 

서로 도달할 수 있는 하나의 그룹내에서는 모든 노드들끼리 서로 도달할 수 있는 것이나 마찬가지다.

 

BFS를 이용해서 1번부터 n번까지 아직 방문하지 않았다면 그룹을 찾는 BFS를 수행해서..

 

visited = [0]*(n+1)

for i in range(1,n+1):
    
    if visited[i] == 0:
        
        visited[i] = 1
        BFS(i,graph)

 

 

하나의 그룹 내에 몇개의 노드들이 존재하는지 찾는다.

 

그 개수가 v개라면... 그 그룹 내에서는 모두 서로 도달가능하므로, vC2개의 노드들끼리 직접 연결하는 간선이 존재해야한다.

 

존재하는 모든 그룹에 대해 vC2개의 합 - 그래프의 간선의 개수 = 문제에서 구하고자하는 경로의 개수

 

from collections import deque
from sys import stdin

def bfs(s,graph):
    
    queue = deque([s])
    
    count = 0

    while queue:
        
        s = queue.popleft()

        for v in graph[s]:

            if visited[v] == 0:

                visited[v] = 1
                count += 1
                queue.append(v)
    
    return count

n,m = map(int,stdin.readline().split())

graph = [[] for _ in range(n+1)]

edge = 0

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

visited = [0]*(n+1)

total = 0

for i in range(1,n+1):
    
    if visited[i] == 0:

        visited[i] = 1
        v = bfs(i,graph)
        v += 1
        total += (v*(v-1)//2)

print(total - edge)