-
Notifications
You must be signed in to change notification settings - Fork 0
/
FOXLINGS.cpp
75 lines (67 loc) · 1.26 KB
/
FOXLINGS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
Problem: https://www.spoj.com/problems/FOXLINGS/
Standard problem for DSU
Author: Prakash Tiwari
*/
#include <iostream>
#include <cstring>
#include <unordered_map>
#define ll long long
using namespace std;
int root(int i, unordered_map <int, int> &m){
while(m[i]!=i){
m[i] = m[m[i]];
i = m[i];
}
return i;
}
void union1(int a, int b, unordered_map <int, int> &m, unordered_map <int, int> &siz){
int ra = root(a, m);
int rb = root(b, m);
if(ra==rb) return;
if(siz[ra]>siz[rb]){
m[rb] = ra;
siz[ra] += siz[rb];
}
else{
m[ra] = rb;
siz[rb] += siz[ra];
}
}
int main(){
int n, ed;
cin>>n>>ed;
unordered_map <int, int> m, siz, vis;
int cnt = 0;
int a, b;
for(int i=0; i<ed; i++){
cin>>a>>b;
if(m.find(a)==m.end()){
cnt++;
m[a] = a;
siz[a] = 1;
vis[a] = 0;
}
if(m.find(b)==m.end()){
cnt++;
m[b] = b;
siz[b] = 1;
vis[b] = 0;
}
union1(a, b, m, siz);
}
int c = 0;
unordered_map <int, int>::iterator it;
for(it = m.begin(); it!=m.end(); it++){
int p = it->first, q = it->second;
if(m.find(p)==m.end()) c++;
else{
int r = root(p, m);
if(vis[r]==0){
c++;
vis[r] = 1;
}
}
}
cout<<c+n-cnt;
}