BOJ 20955번: 민서의 응급 수술

문제 설명

모든 뉴런을 트리 형태로 만들기 위하여 필요한 최소 연산 횟수 구하기

🔗 문제 링크

핵심 아이디어

• ‼️ N개의 뉴런을 모두 트리로 잇기 위한 최소한의 간선 개수 = N-1 ‼️
• DFS로 이미 연결되어있는 그룹 개수 구하기 (k)
• 추가 간선 구하는 법
  • k - 1 (k개의 그룹을 잇기 위해 k-1개의 간선이 필요함)
• 제거 간선 구하는 법
  • 최소한의 간선 개수 (N-1) = 이미 연결된 간선 + 추가 간선 - 제거 간선
  • n - 1 = m + (k-1) - ?
  • ? = m + k - n
• 최소한의 연산 횟수 구하는 법
  • 제거 간선 + 추가 간선
  • (m + k - n) + (k - 1)
  • m + 2k - n - 1

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, u, v;
vector<int> adj[100005];
bool vis[100005];
int k = 0; // 연결된 그룹 개수

void dfs(int cur){
    vis[cur] = true;
    for(int nxt : adj[cur]){
        if (vis[nxt]) continue;
        dfs(nxt);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for(int i = 1; i <= n; i++){
        if (!vis[i]){
            dfs(i);
            k++;
        }
    }
    
    // 제거 간선: m + k - n => (n - 1 = m + k - 1 - ?)
    // 추가 간선: k - 1
    cout << m + k*2 - n - 1;
}