Butterfly

問題描述：有一群旅行愛好者，有一天，他們帶回了n隻蝴蝶回來。他們相信每一隻都屬于兩個不同種類中的一種，為了讨論友善，我們稱它們為A與B。他們想把n隻标本分成兩組——一些屬于A且一些屬于B——但是直接标記任何一個标本對于他們是非常困難，是以他們決定采用下面的方法。

對每對标本i和j，他們細心地把它們放到一起研究。如果他們以自己的判斷足以确信，那麼他們把這對蝴蝶标記為“相同”（這意味着他們相信這兩隻來自同一類）或者是“不同”（這意味着他們相信這兩隻來自不同的類）。他們也可以對某些标本判斷不出來而棄權，在這種情況下，我們稱這對标本是不明确的。

現在他們有n隻标本的集合，還有對那些沒有棄權的标本對的m個判斷的集合（“相同”或者“不同”）。他們想知道這個資料與每隻蝴蝶來自A和B中的一個類的想法是否一緻。更具體地說，如果對每對蝴蝶按照下述方式标記A或B是可能的，即對每個标為“相同”的（i，j）對，就是i與j有相同标記的情況；對每個标為“不同”的（i，j）對，就是i與j有不同标記的情況。那麼我們可以說這m個判斷是一緻的。他們正在冥思苦想自己的判斷是否是一緻的。請你幫他們設計合理的算法解決該問題。

輸入：輸入包含多組資料，以檔案結束符為終止。

每組資料第一行為兩個整數，分别是n和m：

n為蝴蝶的數量，編号從0到n-1

m為關系的數量

接下來是m組關系資料，每組資料占一行，為三個整數，前兩個整數表示蝴蝶的編号，第三個整數為關系的種類（相同或者不同）：

0為相同，1為不同

1 < n <= 1000

1 < m <= 100000

輸出：合理就輸出YES

不合理就輸出NO

樣例輸入：

3 3

0 1 0

1 2 1

0 2 1

3 3

0 1 0

1 2 1

0 2 0

樣例輸出

YES

NO

求解

輸入的是m組關于n個資料點之間的兩兩的關系，關系要麼為一緻，要麼為不一緻，判斷最終生成的關系是否出現沖突，即通過某組關系判斷兩個節點是屬于同一類，然而通過另外一組關系判斷其不屬于同一類的情況，歸根結底就是染色問題。對輸入的的關系，我們對其進行染色，假設一個頂點為顔色1，當兩個頂點一緻時，判斷另外一個頂點是否染色，若未染色另外一個頂點也染為顔色1，若已經染色，則判斷染的顔色是否一緻，不一緻時，break，輸出結果NO；當輸入的兩個頂點不一緻時，判斷另外一個頂點是否染色，若染色，判斷染的顔色是否不一緻，若一緻，則break，輸出NO，若未染顔色，則判斷對另外一個頂點染顔色2，以此類推；采用BFS，上述過程中，記錄所有與“根”（相對的）節點相連的頂點，壓入一個隊列，之後對隊列的所有的元素重複上述過程即可。

整個代碼如下：

#include<stdlib.h>
#include<iostream>
#include<queue>
#include<string>
#include<string.h>

using namespace std;

int n, m;
int relation[][];//表示輸入蝴蝶的關系
int vis[];//用于标記是否已經尋找過該關系
int state[];//用于存儲是每隻蝴蝶的顔色
queue<int> prepare_vist;//建立用于入隊列的準備廣度優先搜尋的對象
int index_1, index_2;
int relation_data;
bool suc;//用于标記是否成功

bool bfs(int node)
{
    //周遊所有與節點i相連的點
    if (vis[node])
        return true;//通路過則直接傳回
    vis[node] = ;
    if (state[node] == )
        state[node] = ;//初始時node未染色，則指派顔色1
    for (int j = ; j < n; j++)
    {
        if (relation[node][j] == )//顔色相異時
        {
            if (!state[j])//未染色
            {
                state[j] =  - state[node];
                prepare_vist.push(j);//節點j與node有關系，入隊
            }
            else if (state[node] == state[j])//出現染色不一緻的情況
            {
                //suc = false;
                return false;
            }
        }
        if (relation[node][j] == )//顔色相同時
        {
            if (state[j] == )
            {
                state[j] = state[node];
                prepare_vist.push(j);
            }
            else if (state[node] != state[j])
            {
                //suc = false;
                return false;
            }
        }
        //relation[node][j]==0，沒有明确的關系，則不能夠确定
    }
    return true;

}

int main()
{
    while (scanf("%d%d", &n,&m) != EOF)
    {
        suc = true;
        memset(relation, , sizeof(relation));
        memset(state, , sizeof(state));
        memset(vis, , sizeof(vis));
        //c++标準庫并不帶有使得隊列元素清空的操作
        while (!prepare_vist.empty())
        {
            prepare_vist.pop();
        }
        for (int i = ; i < m; i++)
        {
            scanf("%d%d%d", &index_1, &index_2,&relation_data);
            relation[index_1][index_2] =  - relation_data;//1為不同，2為相同
            relation[index_2][index_1] =  - relation_data;
        }
        //編寫算法
        for (int i = ; i < n; i++)
        {
            prepare_vist.push(i);//準備周遊的元素入隊
            while (!prepare_vist.empty())
            {
                if (!bfs(prepare_vist.front()))
                {
                    suc = false;
                    break;
                }
                prepare_vist.pop();
            }


        }
        if (!suc)
            cout << "NO" << endl;
        if (suc)
            cout << "YES" << endl;
    }
    return ;
}
           

注意到，輸入的資料可能包含多個連通子圖，是以在初始時，需要指定一個顔色，根據此頂點與其它頂點的關系（把其它頂點依次壓入隊列），來進行染色；對于一個心得并未指派的頂點，應是一個連通子圖中的一個起始頂點，因為如果屬于另外一個已經周遊的連通子圖，其應該被染色，因為總能夠找到一個路徑使得其能夠與起始點連接配接；是以需要進行判斷并且指派：

if (state[node] == )
        state[node] = ;//初始時node未染色，則指派顔色
           

注意到，因為循環中包含了所有頂點的周遊，是以對于兩個頂點，會周遊兩次，但是輸入時僅輸入一個頂點的關系，是以需要在輸入時做一個trick：

for (int i = ; i < m; i++)
        {
            scanf("%d%d%d", &index_1, &index_2,&relation_data);
            relation[index_1][index_2] =  - relation_data;//為不同，為相同
            relation[index_2][index_1] =  - relation_data;//trick
        }
           

另外POJ對于memset必須需要包括頭檔案:

#include<string>
#include<string.h>
           

同時，C++标準庫并沒有直接清空隊列的操作，需要寫一個loop進行清空

while (!prepare_vist.empty())
        {
            prepare_vist.pop();
        }