https://www.acmicpc.net/problem/20955
민서의 응급 수술 문제는 BFS/DFS를 이용하여 해결할 수 있습니다.
모든 뉴런을 하나의 트리 형태로 연결하기 위해서는 흩어져 있는 각각의 그래프가 모두 트리여야, 연결했을 때 트리 형태를 유지할 수 있습니다.
모든 뉴련을 하나의 트리 형태로 연결하기 위한 연산으로, 아래의 두 가지 연산이 있습니다.
- 두 뉴런을 연결한다.
- 이미 연결된 두 뉴런의 연결을 끊는다.
트리는 정점이 N개 일 때, N - 1개의 간선을 갖습니다.
따라서, 각각의 그래프는 N - 1개의 간선을 가지도록 해야합니다.
임의의 그래프의 간선이 N - 1개보다 많으면 2번 연산을 수행하여 연결을 끊어줘야 합니다.
또한, 1번 연산을 수행하여 흩어져 있는 트리를 연결할 수 있습니다.
N개의 트리가 있을 때, 연결에 필요한 연산은 N - 1개입니다.
각각의 그래프에 대해 BFS를 수행하여, 해당 그래프의 간선 개수와 그래프의 개수를 계산할 수 있습니다.
결과적으로, 1번 연산을 수행한 횟수 + 2번 연산을 수행한 횟수를 출력해주면됩니다.
전체 코드는 아래와 같습니다.
#include <bits/stdc++.h>
using namespace std;
int vis[100010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<int>> linked(n + 1); // 인접 리스트
for(int i = 0; i < m; i++){ // 인접 리스트 만들어줌
int u, v; cin >> u >> v;
linked[u].push_back(v);
linked[v].push_back(u);
}
int n_graph = 0; // 그래프의 개수
int n_cycle = 0; // 싸이클의 개수
for(int st = 1; st <= n; st++){
if(vis[st] == 0){ // 아직 방문하지 않은 경우 BFS 수행
n_graph++; // 그래프의 개수 증가
queue<int> q;
q.push(st);
vis[st] = 1;
set<int> vertice; // 해당 그래프에 연결된 정점
vertice.insert(st);
while(!q.empty()){
int cur = q.front(); q.pop();
for(auto nxt : linked[cur]){
if(vis[nxt] != 0) continue; // 이미 방문한 경우 방문하지 않음
q.push(nxt);
vertice.insert(nxt); // 방문한 정점을 저장
vis[nxt] = 1;
}
}
int edges = 0; // 해당 그래프의 간선 개수
for(auto v : vertice) edges += linked[v].size(); // 방문한 정점의 간선 개수를 더해줌
n_cycle += (edges / 2) - (vertice.size() - 1); // 싸이클의 개수
}
}
cout << n_cycle + n_graph - 1 << "\n"; // 싸이클의 개수 + 그래프의 개수 - 1
}
아래는 문제 풀이에 사용된 테스트케이스입니다.
3 2
1 2
2 3
-> 0
8 7
1 3
1 2
2 4
3 4
5 6
5 7
6 7
-> 4
5 6
1 2
1 3
1 4
2 5
3 5
4 5
-> 2
'Algorithm > Tree' 카테고리의 다른 글
[SW Expert Academy 1248번] 공통 조상 (0) | 2022.07.03 |
---|---|
[백준 15681] 트리와 쿼리 (C++) (0) | 2022.06.04 |
[백준 4803번] 트리 (C++) (0) | 2022.06.04 |