백준18452 Free Edges

작성일 | In

문제 링크

  • http://icpc.me/18452

풀이

흰색 간선들이 사이클을 이루면 한 정점에 흰색 간선이 2개 이상 붙기 때문에 불가능합니다. 따라서 흰색 간선은 트리 또는 포레스트를 이루어야 합니다.
Union-Find 등을 이용해 maximum spanning forest의 크기를 구하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int N, M, P[101010], R;
int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
bool Merge(int u, int v){ return Find(u) != Find(v) && (P[P[u]]=P[v], true); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; iota(P+1, P+N+1, 1); R = M;
    for(int i=0,s,e; i<M; i++) cin >> s >> e, R -= Merge(s, e);
    cout << R;
}