二部图(二分图判定--dfs)

题目链接：二部图

二部图

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

难度：1

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

输入

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

输出

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

样例输入

样例输出

NOT BICOLORABLE.

BICOLORABLE.
二分图定义：有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边相连接！

判断二分图的常见方法：开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色，若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

错误代码我也要贴出来，因为wa了十几次了，让司老大看也看不出毛病，求大牛指导。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int maxn = ;

 int color[maxn];

 vector<int> g[maxn];

 int n,m;

 bool dfs(int u,int c){

     color[u] = c;

     for(int i = ; i<g[u].size(); i++){

         if(color[g[u][i]] == c) return false;

         if(color[g[u][i]] ==  && !dfs(g[u][i],-c)) return false;

     }

     return true;

 }

 void solve(){

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

         int x,y;

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

             scanf("%d%d",&x,&y);

             g[x].push_back(y);

             g[y].push_back(x);

         }

         int flag = ;

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

             if(color[i] == ){

                 if(!dfs(i,)){

                     flag = ;

                     break;

                 }

             }

         }

         if(flag) printf("NOT BICOLORABLE.\n");

         else printf("BICOLORABLE.\n");

         memset(color,,sizeof(color));

         for(int i = ; i<=n; i++) g[i].clear();

     }

 }

 int main()

 {

     solve();

     return ;

 }

巴特西

二部图(二分图判定--dfs)

二部图

最新文章

热门文章