Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- int arr[2000090],size[2000090];
- void initialize(int n)
- {
- for(int i=1;i<=n;i++)
- {
- size[i]=1;
- arr[i]=i;
- }
- }
- int root(int i)
- {
- while(arr[i] != i)
- {
- arr[i]=arr[arr[i]];
- i=arr[i];
- }
- return i;
- }
- bool find(int a,int b)
- {
- if(root(a)==root(b))
- return true;
- return false;
- }
- void weighted_union(int a,int b)
- {
- int ra=root(a);
- int rb=root(b);
- if(ra==rb)
- return;
- if(size[ra]<size[rb])
- {
- arr[ra]=arr[rb];
- size[rb]+=size[ra];
- size[ra]=0;
- }
- else
- {
- arr[rb]=arr[ra];
- size[ra]+=size[rb];
- size[rb]=0;
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- map< int,int > mp;
- set<int> s;
- vector< pair<int,int> > vs;
- int n,m;
- cin>>n>>m;
- for(int i=0;i<m;i++)
- {
- int x,y;
- cin>>x>>y;
- s.insert(x);
- s.insert(y);
- vs.push_back(make_pair(x,y));
- }
- auto it = s.begin();
- int c=1;
- vector<int> mem;
- while(it!=s.end())
- {
- mp[*it]=c;
- mem.push_back(*it);
- c++;
- it++;
- }
- int si=s.size(),cc=0;
- initialize(si+100);
- for(int i=0;i<vs.size();i++)
- {
- weighted_union(mp[vs[i].first],mp[vs[i].second]);
- }
- for(int i=1;i<=si;i++)
- {
- if(size[i]!=0)
- cc++;
- }
- cc+=n-s.size();
- cout<<cc<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement