九度oj 题目1027：欧拉回路 【ZJU2008考研机试题2】

           不然老是Runtime Error，叫人检查到吐。。

tip2：无向图是欧拉回路：图连通 且 每个结点的度为偶数(可允许一个顶点有多条偶数边)

          有向图是欧拉回路：图连通 且 每个顶点入度=出度

/*无向图是欧拉回路：图连通 且 每个结点的度为偶数，可允许一个顶点有多条偶数边。有向图是欧拉回路：图连通 且 每个顶点入度=出度
*/
#include <stdio.h>
int degree[3000000],parent[10100],cnt,n;
struct E{int a,b;
}r[1500010];
void init()
{cnt=0;int i;for(i=0;i<=n;i++)degree[i]=0;for(i=0;i<=n;i++) //结点下标从1开始取到n；parent[i]=-1;
}
int findRoot(int tmp)
{if(parent[tmp]==-1)return tmp;else{int tmpRoot=findRoot(parent[tmp]);parent[tmp]=tmpRoot;return tmpRoot;}
}int main()
{int m,i;//freopen("G:\\in.txt","r",stdin); while(scanf("%d",&n)!=EOF){if(n==0) break;init();scanf("%d",&m);for(i=0;i<m;i++){scanf("%d%d",&r[i].a,&r[i].b);  //输入别忘了&！！！degree[r[i].a]++;degree[r[i].b]++;}for(i=0;i<m;i++){int tmpA=findRoot(r[i].a),tmpB=findRoot(r[i].b);if(tmpA!=tmpB)parent[tmpA]=tmpB;}for(i=1;i<=n;i++){if(parent[i]==-1)cnt++;}if(cnt==1){int isOk=1;for(i=1;i<=n;i++){if(degree[i]%2!=0)isOk=0;break;}if(isOk==1)printf("1\n");elseprintf("0\n");}	elseprintf("0\n");}return 0;
}