백준 20955번 민서의 응급 수술[C++/python]

1. 문제 풀이

 connected component의 개수를 깊이 우선 탐색으로 셉니다. ( = group ) 이 그룹들을 모두 연결하기 위해서는 group - 1개의 간선이 필요합니다. 그룹들을 모두 연결했으면 간선의 총개수는 m + group -1 개가 됩니다. 트리의 간선은 n-1개이므로 그 이상의 간선들은 삭제하여야 합니다. 따라서 추가/삭제의 최솟값은 group - 1 + m +group - 1 - (n-1)이 됩니다.

 

2. 코드

2-1. C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const char nl = '\n';
int n, m, u, v;
vector<int> adj[100'005];
vector<bool> vis(100'005);
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);
  }
  int group = 0;
  for(int i = 1; i <= n; i++){
    if(vis[i]) continue;
    group++;
    queue<int> q;
    q.push(i);
    vis[i] = 1;
    while(!q.empty()){
      auto cur = q.front(); q.pop();
      for(auto nxt : adj[cur]){
        if(vis[nxt]) continue;
        q.push(nxt);
        vis[nxt] = 1;
      }
    }
  }
  cout << group - 1 + abs(m+group-n);
}

2-2. Python

#Authored by : chjh2129
import sys

# 재귀 깊이 재설정
sys.setrecursionlimit(100100)

input = sys.stdin.readline

def DFS(cur:int, G:list[list[int]], vis:list[bool]) -> None:
  vis[cur] = True
  for nxt in G[cur]:
    if not vis[nxt]:
      DFS(nxt, G, vis)

def main() -> None:
  # 정점 개수 N, 간선 개수 M
  N, M = map(int, input().split())

  # variables
  G: list[list[int]] = [ [] for _ in range(N+1) ] # Graph
  vis: list[bool] = [ False for _ in range(N+1) ] # visited array

  # input
  for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
  
  # solve
  group:int = 0
  for vertex in range(1, N+1):
    if not vis[vertex]:
      group += 1
      DFS(vertex, G, vis)

  # output
  print((group - 1) + (M + group - 1) - (N - 1))

sys.exit(main())

 

3. 제출 결과