POJ---1308（并查集，判连通，无环）

题意：

给定一组数据（u，v）代表u指向v。判断这组数据是否形成一棵树。

题解：

利用树的特性：连通且无环。或者利用树的性质：无环(或者联通)且v=e+1；

无环可以用并查集去判定。连通可以根据并查集确定有几个根节点来判断。

①：无环。E=V+1。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<stack>using namespace std;int pa[1000];
vector<int>c;int findset(int x)
{return pa[x]==-1? x : pa[x]=findset(pa[x]);
}set<int>s;
int main()
{int u, v;int k=0;while(1){bool flag=true;memset(pa,-1,sizeof(pa));int sum=0;s.clear();int num=0;while(cin>>u>>v,u||v){if(u==-1&&v==-1)return 0;s.insert(u);s.insert(v);num++;if(findset(u)==findset(v))flag=false;//有环else pa[findset(v)]=findset(u);}if((flag&&s.size()==num+1)||s.size()==0)printf("Case %d is a tree.\n",++k);//没有节点也定义为树。elseprintf("Case %d is not a tree.\n",++k);}}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<stack>using namespace std;int pa[1000];
vector<int>c;int findset(int x)
{return pa[x]==-1? x : pa[x]=findset(pa[x]);
}set<int>s;
int main()
{int u, v;int k=0;while(1){bool flag=true;memset(pa,-1,sizeof(pa));int sum=0;s.clear();int num=0;while(cin>>u>>v,u||v){if(u==-1&&v==-1)return 0;s.insert(u);s.insert(v);num++;if(findset(u)==findset(v))flag=false;//有环else pa[findset(v)]=findset(u);}set<int>::iterator it;for(it=s.begin(); it!=s.end(); it++)if(pa[*it]==-1)sum++;if((flag&&sum==1)||s.size()==0)printf("Case %d is a tree.\n",++k);//没有节点也定义为树。elseprintf("Case %d is not a tree.\n",++k);}}