문제 출처

1. 문제설명

  • 그래프가 여러개 주어진다.
  • 이 그래프를 트리로 변환하고, 하나로 잇고자 한다.
  • 하나의 트리로 만들기 위해서 드는 비용은?
    • 연산 한번에 1이다.
  • 문제 분류
    • Data Structure, Graph, Tree, Disjoint Set


2. 알고리즘 설계

  • DFS로 트리의 개수를 세준다.
    • DFS의 실행횟수 == 트리의 개수(cnt)
  • 하나의 트리니까 cnt-1을 하면 될 줄 알았다.
  • 정답값 출력
    • 최종 그래프는 cnt-1개의 간선을 추가해서 m+cnt-1개의 간선을 가지고 있다.
    • 트리는 n-1개의 간선을 가진다. (두 뉴런 사이에는 최대 1개의 시냅스만 존재한다.)
    • 그렇기 때문에 (m+groupcnt-1)-(n-1)개의 간선을 제거해야 한다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100'005;
int n, m, u, v, cnt;
vector<int> adj[SZ];
bool vis[SZ];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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]) continue;
        dfs(i);
        cnt++;
    }

    cout << (cnt-1) + (m+cnt-1)-(n-1);

    return 0;
}