DFS-UVA10004-Bicoloring

朴灿烈づ我的快乐病毒、 2022-05-14 22:08 129阅读 0赞

*  # DFS-UVA10004-Bicoloring #

--------------------

*  ## 题目链接：[10004 - Bicoloring][] ##
 *  ## 思路： ##

题目大意是有N个点，L组数据，每组数据有两个数a，b 表示编号为a，b的点相连，用两种颜色填充这些点，并且满足相连的点不能同色，如果满足，输出BICOLORABLE.，否则输出NOT BICOLORABLE.

深搜的题目，数据量不大，***用邻接矩阵表示点的连接***

深搜对每个点涂色，**用-1，1涂**，**0代表该点没有涂色**，如果出现相连两个点同色，直接false

*  ## 代码： ##

#include<iostream>
    #include<memory.h>
    using namespace std;
    #define MAX_SiZE 205
    int Grapth[MAX_SiZE][MAX_SiZE];  //邻接矩阵
    int Color[MAX_SiZE];   //标记每个点的颜色
    int N,L;
    
    bool DFS(int Index)
    {
        for(int i=0;i<N;i++)    //对每个点的相邻点进行遍历
        {
            if(Grapth[Index][i])
            {
                if(!Color[i])   //相邻点还没涂色
                {
                    Color[i]=-1*Color[Index];   //涂成相反颜色
                    if(DFS(i)==false)     //无法满足相邻不同色，false
                        return false;
                }
                else if(Color[Index]==Color[i])   //相邻点涂色了，并且于当前点颜色相同，false
                    return false;
            }
        }
        return true;
    }
    
    int main()
    {
        while(cin>>N&&N)
        {
            memset(Color,0,sizeof(Color));   //初始化
            memset(Grapth,0,sizeof(Grapth));
            int a,b;
            cin>>L;
            for(int i=0;i<L;i++)  //构建邻接矩阵
            {
                cin>>a>>b;
                Grapth[a][b]=Grapth[b][a]=1;  
            }
            Color[0]=1;   //对第一个点上色
            if(DFS(0))
                cout<<"BICOLORABLE."<<endl;
            else
                cout<<"NOT BICOLORABLE."<<endl;
        }
        return 0;
    }

[10004 - Bicoloring]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=945