백준 24542번 튜터-튜티 관계의 수 파이썬

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

24542번: 튜터-튜티 관계의 수

 

내 답안

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]

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

visited = [0] * (N + 1)

def bfs(v):
    visited[v] = 1
    lst.append(0)
    q = deque()
    q.append(v)

    while q:
        p = q.popleft()
        for next_p in graph[p]:
            if not visited[next_p]:
                q.append(next_p)
                visited[next_p] = 1
                lst.append(0)

cnt = 1
lst = []
for i in range(1, N + 1):
    if not visited[i]:
        bfs(i)
        cnt *= len(lst) # 경우의수 구하기
        lst = []

print(cnt % 1000000007)

---

'

문제 아이디어 구상은 간단했다.

그냥 연결 요소들을 나누어 준다음, 그 나눈 연결 요소들을 센 다음 곱해주면 된다.

예를들어 그래프가  ●-●-●     ●-●-●-●  이런식으로 있다면 경우의 수는 3x4 인 12가 답이된다.

 

연결 요소들을 세는 건 lst에 0을 넣어 개수를 파악하였고 len(lst)는

한번 BFS가 끝나면 lst를 초기화하는 코드를 짰다.

 

처음엔 DFS를 이용하여 풀었지만 시간 초과로 해결하지 못하였다.

그래서 BFS로 바꿔서 풀었더니 해결이 되었다.