백준 11724번: 연결 요소의 개수

본 포스팅은 문제의 풀이 보단 작성자의 개인적인 정리에 가깝습니다.
그냥 이 사람은 이렇게 풀었구나 정도로 봐주시면 감사하겠습니다

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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

예제 입력 3

6 3
1 3
2 3
3 4

예제 출력 3

3

예제 입력 4

3 0

예제 출력 4

3

 

풀이

import sys

ver,edge = list(map(int,sys.stdin.readline().split()))

compo = []
not_visited = [x+1 for x in range(ver)]
for i in range(edge):
    v1,v2 = list(map(int,sys.stdin.readline().split()))
    compo.append((v1,v2))
    if(v1 in not_visited):
        not_visited.remove(v1)
    if(v2 in not_visited):
        not_visited.remove(v2)
compo = sorted(compo)
if(len(compo)>0):
    result = [set([compo[0][0],compo[0][1]])]
    compo.pop(0)

    # print(visited)
    for i, data in enumerate(compo):
        v1,v2 = data
        check = True
        for i in range(len(result)):
            if(v1 in result[i] or v2 in result[i]):
                result[i].add(v1)
                result[i].add(v2)
                check=False
                break
        if(check):
            result.append(set([v1,v2]))
    # print(result,not_visited)
    print(len(result)+len(not_visited))
else:
    print(len(not_visited))

 

답은 위와 같습니다

연결된 요소들의 개수를 세어주면 됩니다.

먼저 연결될 수 없는 정점들을 모두 세어줍니다. (이들은 방문되지 않은 정점들입니다.)

이후, 연결된 정점들을 하나씩 체크하면 되는데, 이를 위해 result 리스트를 사용합니다. result는 연결된 정점들을 하나의 집합으로 봅니다.

result 리스트는 각각의 연결 요소를 저장하는 리스트입니다. 각 연결 요소는 정점들의 집합으로 표현됩니다. 새로운 정점을 탐색하면서, 이 정점이 이미 존재하는 연결 요소에 속해 있는지 확인하고, 속해 있다면 해당 연결 요소에 정점을 추가합니다. 만약 속해 있지 않다면 새로운 연결 요소를 추가합니다.