本文主要是介绍hdu 1232——畅通工程 (无优化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
并查集
这道题优化效果不明显
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int father[1005];int getfather(int i)
{while(father[i]!=-1){i=father[i];}return i;
}void Union(int x,int y)
{int fx=getfather(x);int fy=getfather(y);if(fx==fy)return ;elsefather[fx]=fy;
}int main()
{int n,m;int i,j;while(cin>>n&&n){cin>>m;memset(father,-1,sizeof(father));for(i=1;i<=m;i++){int x,y;cin>>x>>y;Union(x,y);}int num[1005];memset(num,0,sizeof(num));for(i=1;i<=n;i++)num[getfather(i)]=1;int sum=-1;for(i=1;i<=n;i++)if(num[i])sum++;cout<<sum<<endl;}return 0;
}
这篇关于hdu 1232——畅通工程 (无优化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!