二分图染色

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int color[1010];  
 4 int a,b,c,d,e,f;
 5 int map1[1001][1001];   　　//用临界矩阵存图
 6 bool DFS(int s)             //DFS搜索节点的染色情况
 7 {
 8     queue<int>q; 
 9     q.push(s);
10     color[s]=1;          //将每个初始点的color值赋值为1.
11     while(!q.empty())
12     {
13         int t=q.front();
14         q.pop();
15         for(int i=1; i<=a; i++)
16         {
17             if(map1[t][i]&&color[i]==-1)
18             {
19                 q.push(i);
20                 color[i]=1-color[t];    //将节点t的相关联的节点的color值赋值成为0.
21             }
22             if(map1[t][i]&&color[i]==color[t])
23             {
24                 return 0;   // 如果t节点的相关连的节点的color值与t点的相等，此图就不是二分图.
25             }
26         }
27     }
28     return 1;
29 }
30 int main()
31 {
32     scanf("%d%d",&a,&b);
33     memset(color,-1,sizeof(color));
34     for(int i=1; i<=b; i++)
35     {
36         scanf("%d%d",&c,&d);
37         map1[c][d]=map1[d][c]=1;   //双向边
38     }
39     int flag=0;
40     for(int i=1; i<=a; i++)
41     {
42         if(color[i]==-1&&DFS(i)==0)
43         {
44             flag=1;
45             break;
46         }
47     }
48     if(flag==0)     //如果是二分图，因为我们已经在DFS函数中将各个染色成为0,1的两种颜色，
49                         //    所以我们判断点是否属于同一个集合就只要判断color值是不是相等就行了。
50     {
51         queue<int>l,k;
52         int num1,num2;
53         num1=num2=0;
54         for(int i=1; i<=a; i++)
55         {
56             if(color[i]==1)  //判断条件
57             {
58                 num1++;
59                 l.push(i);
60 
61             }
62             else if(color[i]==0)    //判断条件
63             {
64                 num2++;
65                 k.push(i);
66             }
67         }
68         printf("%d\n",num1);
69         while(!l.empty())
70         {
71             printf("%d ",l.front());
72             l.pop();
73         }
74         printf("\n%d\n",num2);
75         while(!k.empty())
76         {
77             printf("%d ",k.front());
78             k.pop();
79         }
80     }
81     else
82         printf("-1\n");
83     return 0;
84 }
85  

#include<bits/stdc++.h>
using namespace std;
#define maxn 100006
int color[maxn];
vector<int>q[maxn];
int a,b,c,d,e,f;
bool DFS(int s)
{
    queue<int>que;
    que.push(s);
    color[s]=1;
    while(!que.empty())
    {
        int t=que.front();
        que.pop();
        for(int i=0; i<q[t].size(); i++)
        {
            int x=q[t][i];
            if(color[x]==-1)
            {
                color[x]=1-color[t];
                que.push(x);
            }
            if(color[x]==color[t])
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d",&a,&b);
    memset(color,-1,sizeof(color));
    for(int i=1; i<=b; i++)
    {
        scanf("%d%d",&c,&d);
        q[c].push_back(d);
        q[d].push_back(c);
    }
    int flag=0;
    for(int i=1; i<=a; i++)
    {
        if(color[i]==-1&&DFS(i)==0)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)
    {
        queue<int>l,k;
        int num1,num2;
        num1=num2=0;
        for(int i=1; i<=a; i++)
        {
            if(color[i]==1)
            {
                num1++;
                l.push(i);

            }
            else if(color[i]==0)
            {
                num2++;
                k.push(i);
            }
        }
        printf("%d\n",num1);
        while(!l.empty())
        {
            printf("%d ",l.front());
            l.pop();
        }
        printf("\n%d\n",num2);
        while(!k.empty())
        {
            printf("%d ",k.front());
            k.pop();
        }
    }
    else
        printf("-1\n");
    return 0;
}