二分图判定 nyoj1015（模板）

深藏阁楼爱情的钟 2022-08-27 15:50 183阅读 0赞

题目：[点击打开链接][Link 1]nyoj1015

分析；题意很清楚，就是让判断一个图是不是二分图，思路当然就是染色法，首先给一个顶点然色，然后与它相邻的顶点全部染相反的颜色，如果过程中发现要染的点已经染色了，而且是和现在点相同的颜色的话，那么就说明不是一个二分图。

其实就是广搜模板

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    const int N = 220;
    vector <int> v[N];
    int col[N];
    bool BFS(int st)
    {
        col[st]=1;
        queue<int> q;
        q.push(st);
        while(!q.empty())
        {
            int k=q.front();
            q.pop();
            //printf("%d %d\n",k,col[k]);
            for(int i=0;i<v[k].size();i++)
            {
                int point=v[k][i];
                int cc=col[k]==1?2:1;
                //printf("--%d %d %d\n",point,col[point],cc);
                if(col[point]==0){
                    col[point]=cc;
                    q.push(point);
                }
                else if(col[point]!=cc){
    
                    return false;
                }
            }
        }
        return true;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d",&n) && n)
        {
            scanf("%d",&m);
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                v[x].push_back(y);
                v[y].push_back(x);
            }
            memset(col,0,sizeof(col));
            if(BFS(0))
                printf("BICOLORABLE.\n");
            else
                printf("NOT BICOLORABLE.\n");
            for(int i=0;i<=n;i++)  //切记
                v[i].clear();
        }
        return 0;
    }

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <queue>
    #define CLR(arr,val) memset(arr,val,sizeof(arr))
    using namespace std;
    
    const int N=205;
    int color[N],n,m;
    bool vis[N];
    vector<int> map[N];
    
    bool bfs(int s){
        queue<int> q;
        q.push(s);color[s]=1;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            if(!vis[now]){
            int len=map[now].size();
            for(int i=0;i<len;i++){
                int des=map[now][i];
                q.push(des);
                if(color[des]==-1)
                color[des]=color[now]==0?1:0;
                else {
                    if(color[des]==color[now]) return false;
                    else continue;
                }
            }
            vis[now]=true;
            }
        }
        return true;
    }
    
    int main(){
        while(~scanf("%d%d",&n,&m)){
            CLR(color,-1);CLR(vis,0);
            CLR(map,0);
            for(int i=1;i<=m;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                map[a].push_back(b);
                map[b].push_back(a);
            }
            bool flag=bfs(0);
            if(!flag){
                printf("NOT BICOLORABLE.\n\n");
            }
            else printf("BICOLORABLE.\n");
        }
        return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1015