UVA 10004 Bicoloring（DFS染色）

题意：

给N个点构成的无环无向图，并且保证所有点对都是连通的。

给每个点染色，要么染成黑要么染成白。问是否存在染色方案使得所有有边相连的点对颜色一定不一样。

是输出 BICOLORABLE 否则输出 NOT BICOLORABLE

思路：

从某点开始，直接进行染色，如果矛盾，返回false。

代码：

int n,l;

vector<int> graph[205];

int color[205];

bool dfs(int u,int fa){

    if(color[fa]==0)

        color[u]=1;

    else

        color[u]=0;

    int L=graph[u].size();

    rep(i,0,L-1){

        int v=graph[u][i];

        if(v!=fa){

            if(color[v]==-1)

                dfs(v,u);

            else

                if(color[v]+color[u]!=1) return false;

        }

    }

    return true;

}

int main(){

    int start;

    while(scanf("%d",&n)!=EOF,n){

        scanf("%d",&l);

        rep(i,0,n-1) graph[i].clear();

        mem(color,-1); color[n]=0;

        while(l--){

            int u,v;

            scanf("%d%d",&u,&v); start=u;

            graph[u].push_back(v);

            graph[v].push_back(u);

        }

        bool yes=dfs(start,n);

        if(yes)

            puts("BICOLORABLE.");

        else

            puts("NOT BICOLORABLE.");

    }

}

巴特西

UVA 10004 Bicoloring（DFS染色）

最新文章

热门文章