オーラ図_オーラかいろ
1925 ワード
source
Description
オラ回路とは、ペンを紙面から離さず、図中の各エッジを1回だけ描くことができ、起点に戻ることができる回路のことです.今、オラ回路があるかどうかを尋ねる図を与えます.Inputテスト入力には、いくつかのテスト例が含まれています.各試験例の1行目には、ノード数N(1
3 3 1 2 1 3 2 3 3 2 1 2 2 3 0
Sample Output
1 0
题解:.題意からG無方向図を知る.Gはオーラ図であり、Gが連通図であり、奇数度ノード(Gの全ノード度数が偶数)を含まない場合のみである.連通図判定は併用してセットを調べることができる.すべての頂点の度数は配列で記録し、配列全体を巡って奇度定点が含まれているかどうかを判定することができる.
#include
#include
#include
#include
using namespace std;
int *parent,*grade,*degree,component;
int father(int v)
{
while(parent[v]!=v)
{
parent[v]=parent[parent[v]];//
v=parent[v];
}
return v;
}
bool isConnected(int v,int w)
{
return father(v)==father(w);
}
void connect(int v,int w)
{
int fathev=father(v);
int fathew=father(w);
if(fathev==fathew) return;
if(grade[fathev]>grade[fathew])
{
parent[fathew]=fathev;
grade[fathev]+=grade[fathew];
}
else{
parent[fathew]=fathev;
grade[fathew]+=grade[fathev];
}
component--;//
}
int main()
{
int n,e,v,w;
while(scanf("%d",&n))
{
if(!n) break;
scanf("%d",&e);
degree=new int[n];
memset(degree,0,sizeof(int)*n);
parent=new int[n];
grade=new int[n];
component=n;
for(int i=0;i