http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1351
这道题先利用并查集的知识点，把输入的数据连结起来，形成一个树，然后再逐个结点判断。如果所有的结点都能相连，那么这是一个连通的路径，否则直接跳出，输出。否则记录结点的度的个数，逐个检查。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int fa[],a[];
int fin(int x)//查找两个结点是否出自同一个父亲节点
{
return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);
}
int unin(int x,int y)//将有关联两个节点连结在一起
{
return fa[fin(y)]=fin(x);
}
int main()
{ int m,n;
while(cin>>m>>n){
memset(a,,sizeof(a));
memset(fa,,sizeof(fa));
for(int i=;i<=m;i++){
fa[i]=i;/初始化父亲节点
}
int x;int y;
for(int i=;i<=n;i++){
cin>>x>>y;
if(fin(x)!=fin(y)){//如果两个节点还没有出自同一个结点，那么
unin(x,y);//吧这两个节点连结在一起
}
a[x]++;//同时记录结点的度数
a[y]++;//同时记录结点的度数
}
int sum1=;
for(int i=;i<=m;i++){
if(a[i]%!=){
sum1++;
} }
int flag=;
for(int i=;i<=m;i++){
if(fin(i)!=fin()){//如果结点并不是相连续的，那么
flag=;//记录flag的值
break;//跳出
}
}
if(flag==)
{
printf("Graph is not connected!\n");
continue;
}
if(sum1==)
{
printf("have Euler path\n");
}
else if(sum1==)
{
printf("have Euler Circuit\n");
}
else
{
printf("have no Euler path\n");
} }
return ;
}