[백준 20955번] 민서의 응급 수술 (C++)

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

20955번: 민서의 응급 수술

---

민서의 응급 수술 문제는 BFS/DFS를 이용하여 해결할 수 있습니다.

 

모든 뉴런을 하나의 트리 형태로 연결하기 위해서는 흩어져 있는 각각의 그래프가 모두 트리여야, 연결했을 때 트리 형태를 유지할 수 있습니다. 

 

모든 뉴련을 하나의 트리 형태로 연결하기 위한 연산으로, 아래의 두 가지 연산이 있습니다.

1. 두 뉴런을 연결한다.
2. 이미 연결된 두 뉴런의 연결을 끊는다. 

트리는 정점이 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