判断二分图染色法 NYOJ 1015

深藏阁楼爱情的钟 2022-06-03 01:36 192阅读 0赞

## 二部图 ##

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

难度：1

描述

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

输入

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

输出

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

样例输入

330 11 22 0320 10 2

样例输出

NOT BICOLORABLE.BICOLORABLE.

判断条件

1.如果节点没有染过色，就染上与它相反的颜色，推入队列，

2.如果节点染过色且相反，忽视掉

3.如果节点染过色且与父节点相同，证明不是二分图，return false

#include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector <int> map[205];
    int n,color[205];
    bool bfs()
    {
    	queue<int>q;
    	color[0]=1;
    	q.push(0);
    	while(!q.empty())
    	{
    		int v1=q.front();
    		q.pop();
    		for(int j=0;j<map[v1].size();j++)
    		{
    			int v2=map[v1][j];
    			if(color[v2]==-1)
    			{
    				color[v2]=-color[v1];
    				q.push(v2);						
    			}
    			else if(color[v2]==color[v1])
    			return false;
    		}
    	}	
    	return true;
    }
    int main()
    {
    	int n,i,j,x,y,m;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    	 	memset(color,-1,sizeof(color));
    	 	for(i=0;i<205;i++)
    	 	map[i].clear();
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d",&x,&y);
    			map[x].push_back(y);
    			map[y].push_back(x);
    		}				
    		if(bfs())
    		printf("BICOLORABLE.\n");
    		else
    		printf("NOT BICOLORABLE.\n");
    	}
    }

还有个不开vector的~

#include<stdio.h>  
    #include<string.h>  
    #include<queue>  
    #include<iostream>  
    using namespace std;  
    int map[205][205],vis[205],n;  
    bool bfs()
    {  
        queue<int>q;  
        memset(vis,0,sizeof(vis));  
        q.push(0); 
    	vis[0]=1;  
        while(!q.empty())  
        {  
            int p=q.front(); 
    		q.pop();  
            for(int j=0;j<n;j++) 
    		{
    			if(map[p][j])  
    	        {  
    	            if(vis[j]==0)  
    	            {  
    	            	vis[j]=-vis[p]; 
    	                q.push(j);  
    	            }  
    	            else if(vis[j]==vis[p])  
    	            return false;  
    	        }  
    		}         
        }  
        return true;  
    }  
    int main()  
    {  
        int m,a,b,i;  
        while(scanf("%d%d",&n,&m)!=EOF)  
        {  
            memset(map,0,sizeof(map));  
            for(i=0;i<m;i++) 
            {  
                scanf("%d%d",&a,&b);  
                map[a][b]=map[b][a]=1;  
            }  
            if(!bfs()||n==1)  
            printf("NOT BICOLORABLE.\n"); 
            else
            printf("BICOLORABLE.\n");
        }  
    }