Nyoj 751 破坏城市[逆并查集]

本文主要是介绍Nyoj 751 破坏城市[逆并查集]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

思路：很是简单，破坏前N条路就是链接后M-N条路？对吧？

 
#include<cstdio>
const int N=10005;
const int M=100005;
int n,m,father[N];
struct Rode
{int a,b;
}rode[M];
void Init()
{for(int i=0;i<n;i++)father[i]=i;
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int a,int b)
{int x=find(a);int y=find(b);if(x!=y)father[x]=y;
}
int main()
{while(~scanf("%d%d",&n,&m)){Init();int num=n,i;for(i=0;i<m;i++)scanf("%d%d",&rode[i].a,&rode[i].b);int stack[M],top=0;for(i=m-1;i>=0;i--){int a=find(rode[i].a);int b=find(rode[i].b);
//            if(i==0) printf("(%d %d)\n",a,b);if(a!=b) stack[top++]=num--;else stack[top++]=num;Union(rode[i].a,rode[i].b);}for(i=m-1;i>=0;i--)printf("%d\n",stack[i]);
//        printf("%d\n",n);}return 0;
}        

一开始，我能说我把stack的数组开成N了吗？WA了我很多次才发现。又是细节。

这篇关于Nyoj 751 破坏城市[逆并查集]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---