8040 : 도로 건설
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
수악나라에는 $N$개의 도시와 이들을 잇는 $M$개의 양방향 도로가 있습니다.
임의의 도시에서 다른 모든 도시로 도로를 통해 갈 수 있도록 나라를 통합하려고 합니다.
이를 위해 추가해야 하는 최소 도로의 개수 $K$를 구하고, 새로 건설해야 할 도로 쌍들을 구하는 프로그램을 작성하시오. (답이 여러 개일 경우 아무거나 하나만 출력합니다.)
[제약 조건]
• $1 \le N \le 100{,}000$
• $0 \le M \le 200{,}000$
• $1 \le a, b \le N$
임의의 도시에서 다른 모든 도시로 도로를 통해 갈 수 있도록 나라를 통합하려고 합니다.
이를 위해 추가해야 하는 최소 도로의 개수 $K$를 구하고, 새로 건설해야 할 도로 쌍들을 구하는 프로그램을 작성하시오. (답이 여러 개일 경우 아무거나 하나만 출력합니다.)
[제약 조건]
• $1 \le N \le 100{,}000$
• $0 \le M \le 200{,}000$
• $1 \le a, b \le N$
입력 설명
첫째 줄에 도시의 수 $N$과 현재 도로의 수 $M$이 공백으로 구분되어 주어집니다. ($1 \le N \le 100,000$, $0 \le M \le 200,000$)
다음 $M$개의 줄에 걸쳐 각 도로가 연결하는 두 도시의 번호 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
다음 $M$개의 줄에 걸쳐 각 도로가 연결하는 두 도시의 번호 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
출력 설명
첫째 줄에 추가해야 할 최소 도로의 수 $K$를 출력합니다.
다음 $K$개의 줄에 걸쳐 새로 건설할 도로가 잇는 두 도시의 번호를 공백으로 구분하여 출력합니다.
다음 $K$개의 줄에 걸쳐 새로 건설할 도로가 잇는 두 도시의 번호를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 2
1 2
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2 3도움
이 문제는 그래프의 서로 연결되지 않은 요소(Connected Components)들의 개수를 구하고, 이들을 하나로 잇는 최소 개수의 간선을 찾는 문제입니다.
서로 다른 컴포넌트들의 개수가 $C$개라면, 최소 $C-1$개의 도로를 건설해야 전체가 연결됩니다.
Union-Find 또는 DFS/BFS를 통해 각 컴포넌트별 대표 정점 리스트 $x_1, x_2, \ldots, x_C$를 구한 후, 인접한 두 대표 정점 간에 $(x_i, x_{i+1})$ 도로를 하나씩 놓아 연결하면 해결됩니다.
서로 다른 컴포넌트들의 개수가 $C$개라면, 최소 $C-1$개의 도로를 건설해야 전체가 연결됩니다.
Union-Find 또는 DFS/BFS를 통해 각 컴포넌트별 대표 정점 리스트 $x_1, x_2, \ldots, x_C$를 구한 후, 인접한 두 대표 정점 간에 $(x_i, x_{i+1})$ 도로를 하나씩 놓아 연결하면 해결됩니다.