Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using pii = pair<int,int> ;
- int parent[100010];
- int find(int u){
- if(parent[u]==u){
- return u;
- }
- return parent[u] = find(parent[u]);
- }
- int n ,m;
- void merge(int u,int v){
- u=find(u);
- v=find(v);
- if(u==v){
- return;
- }
- --n;
- if(u>v){
- parent[v]=u;
- }
- else{
- parent[u]=v;
- }
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i){
- parent[i]=i;
- }
- int u ,v;
- vector<pii> bridge;
- for(int i=1;i<=m;++i){
- scanf("%d%d",&u,&v);
- bridge.push_back(make_pair(u,v));
- }
- int cnt=0;
- for(int i=m-1;i>=0;--i){
- if(n==1){
- break;
- }
- int start=bridge[i].first;
- int end1 =bridge[i].second;
- merge(start,end1);
- ++cnt;
- }
- cout << m-cnt;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement