문제:
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1<=N<=1,000, 0<=M<=Nx(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1<=u,v<=N, u!=v) 같은 간선은 한 번만 주어진다.
출력:
첫째 줄에 연결 요소의 개수를 출력한다.
풀이방법:
인접리스트와 dfs를 사용해서 이 문제를 사용했다. N, M을 입력받은 뒤에 인접리스트 U를 초기화하고, visited 배열을 초기화 했다. 방문하지 않은 정점에 대해서만 dfs를 수행해서 연결 요소의 개수를 구했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import sys
sys.setrecursionlimit(10000)
def dfs(i):
visited[i]=1
for n in U[i]:
if visited[n]==0:
dfs(n)
N, M=map(int,input().split())
U = [[]for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
s,e = map(int,input().split())
U[s].append(e)
U[e].append(s)
answer= 0
for i in range(1,N+1):
if visited[i]==0:
answer+=1
dfs(i)
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주��
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]16561. 3의 배수 (0) | 2020.09.01 |
|---|---|
| [BOJ]10989. 수 정렬하기3 (0) | 2020.08.27 |
| [BOJ]1717. 집합의 표현 (0) | 2020.08.20 |
| [BOJ]14502. 연구소 (0) | 2020.08.18 |
| [BOJ]2961. 도영이가 만든 맛있는 음식 (0) | 2020.08.13 |