nyoj1015——二分图染色

二部图

时间限制：1000 ms | 内存限制：65535 KB

难度：1

描述: 二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同，切任意两个结点之间最多一条边。为了简化问题，我们每次都从0节点开始涂色

输入

输入：
多组数据
第一行一个整数 n(n<=200) 表示 n个节点
第二行一个整数m 表示条边
随后 m行两个整数 u , v 表示一条边

输出

如果是二部图输出 BICOLORABLE.否则输出 NOT BICOLORABLE.

样例输入

样例输出

NOT BICOLORABLE.

BICOLORABLE.

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int INF = 0x3f3f3f3f;

const int maxn = ;

int V;

int vis[maxn];

vector<int>v[maxn];

int flag;

void dfs(int x)

{

    for(int i=;i < v[x].size();i++){

        if(vis[v[x][i]] == vis[x]) flag = ;

        if(vis[v[x][i]] == -){

            vis[v[x][i]] = (vis[x]?:);

            dfs(v[x][i]);

        }

    }

}

int main()

{

    int m;

    while(~scanf("%d%d",&V,&m)) {

        memset(v,, sizeof(v));

        for(int i=;i < V;i++){   //未访问过的标记为-1

            vis[i] = -;

        }

        vis[] = ;

        flag = ;

        for (int i = ; i < m; i++) {

            int a, b;

            scanf("%d%d", &a, &b);

            v[a].push_back(b);

            v[b].push_back(a);

        }

        dfs();

        if(flag == )

            printf("NOT BICOLORABLE.\n");

        else

            printf("BICOLORABLE.\n");

    }

    return ;

}

——一开始漏了~，疯狂T，好气啊.