Uva-11396-Claw Decomposition
1390 단어 이분도 판정
코드:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=310;
const int maxm=5e4;
int e,m,n,pnt[maxm],nxt[maxm],head[maxn],color[maxm];
struct Node
{
int from;
int to;
}E[maxm];
void AddEdge(int u,int v)
{
pnt[e]=v;nxt[e]=head[u];head[u]=e++;
pnt[e]=u;nxt[e]=head[v];head[v]=e++;
}
void Build()
{
e=0;
memset(head,-1,sizeof(head));
memset(color,0,sizeof(color));
for(int i=0;i<m;i++)
AddEdge(E[i].from,E[i].to);
}
bool bipartite(int u)
{
for(int i=head[u];i!=-1;i=nxt[i])
{
if(color[pnt[i]]==color[u])
return false;
if(!color[pnt[i]])
{
color[pnt[i]]=3-color[u];
if(!bipartite(pnt[i]))
return false;
}
}
return true;
}
int main()
{
while(scanf("%d",&n)&&n)
{
m=0;
while(scanf("%d%d",&E[m].from,&E[m].to)&&E[m].from+E[m++].to);
m--;
if(2*m!=3*n)
{
printf("NO
");
continue;
}
Build();
color[1]=1;
if(bipartite(1))
printf("YES
");
else
printf("NO
");
}
return 0;
}