二分図染色例

二分図染色例
二分図染色水問題——CFが図の問題を解決する際にまず考慮するのは、図一、隣接行列という問題のデータが二次元配列で図を作ることをサポートしていないが、問題を作るために問題を作るのではないか.私はわざわざ隣接行列WAを使います.直接コード:ここの結果はWA 12...

#include
using namespace std;
int color[1010];  
int a,b,c,d,e,f;
int map1[1001][1001];   / /       
bool DFS(int s)             //DFS         
{
    queueq; 
    q.push(s);
    color[s]=1;          //       color    1.
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=1; i<=a; i++)
        {
            if(map1[t][i]&&color[i]==-1)
            {
                q.push(i);
                color[i]=1-color[t];    //   t        color     0.
            }
            if(map1[t][i]&&color[i]==color[t])
            {
                return 0;   //   t          color  t    ，        .
            }
        }
    }
    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);
        map1[c][d]=map1[d][c]=1;   //   
    }
    int flag=0;
    for(int i=1; i<=a; i++)
    {
        if(color[i]==-1&&DFS(i)==0)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)     //      ，       DFS          0,1     ，
    					//	                     color         。
    {
        queuel,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
",num1);
        while(!l.empty())
        {
            printf("%d ",l.front());
            l.pop();
        }
        printf("
%d
",num2);
        while(!k.empty())
        {
            printf("%d ",k.front());
            k.pop();
        }
    }
    else
        printf("-1
");
    return 0;
}
 

個人的には隣接行列がわかりやすいと感じたので無理やりコメント...
二、隣接表はちょうど今日vectorが直接vectorで2つの点の間の連絡Acceptedを創立することを理解したばかりです.
上のコードと似ているようですね～実は注釈がおっくうです

#include
using namespace std;
#define maxn 100006
int color[maxn];
vectorq[maxn];
int a,b,c,d,e,f;
bool DFS(int s)
{
    queueque;
    que.push(s);
    color[s]=1;
    while(!que.empty())
    {
        int t=que.front();
        que.pop();
        for(int i=0; il,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
",num1);
        while(!l.empty())
        {
            printf("%d ",l.front());
            l.pop();
        }
        printf("
%d
",num2);
        while(!k.empty())
        {
            printf("%d ",k.front());
            k.pop();
        }
    }
    else
        printf("-1
");
    return 0;
}