九度OnlineJudgeの1027:オラ回路
タイトルの説明:
オラ回路とは、ペンを紙面から離さず、図中の各エッジを1回だけ描くことができ、起点に戻ることができる回路のことです.今、オラ回路があるかどうかを尋ねる図を与えます.
入力:
テスト入力には、いくつかのテスト例が含まれます.各試験例の1行目には、ノード数N(1出力:
各試験例の出力は1行を占め、オーラ戻り路が存在する場合は1を出力し、そうでない場合は0を出力する.
サンプル入力:
サンプル出力:
オラ回路とは、ペンを紙面から離さず、図中の各エッジを1回だけ描くことができ、起点に戻ることができる回路のことです.今、オラ回路があるかどうかを尋ねる図を与えます.
入力:
テスト入力には、いくつかのテスト例が含まれます.各試験例の1行目には、ノード数N(1
各試験例の出力は1行を占め、オーラ戻り路が存在する場合は1を出力し、そうでない場合は0を出力する.
サンプル入力:
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0// ( ) : + ( ， Degree inDegree outDegree )サンプル出力:
1
0#include <iostream>
#define MAX 1001
using namespace std;
int Tree[MAX];
int Degree[MAX];
int findRoot(int x)
{
if(Tree[x]==-1) return x;
else
{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main()
{
int N;
int M;
while(cin>>N,N!=0)
{
cin>>M;
for(int i=1;i<=N;++i)
{
Tree[i]=-1;
Degree[i]=0;
}
int a,b;
while(M--)
{
cin>>a>>b;
++Degree[a];
++Degree[b];
int x = findRoot(a);
int y = findRoot(b);
if(x!=y)
{
Tree[x] = y;
}
}
int ans = 0;
int flag = 1;
for(int i=0;i<=N;++i)
{
if(Tree[i]==-1) ans++;
if(Degree[i]%2==1) flag=0;
}
if(ans!=1) flag=0;
cout<<flag<<endl;
}
// system("PAUSE");
return 0;
}