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; }

좋은 웹페이지 즐겨찾기