[HOJ] 95 - 議會設置

Problem : 95 - 議會設置

Special Judge

Problem：

兔子國統治了銀河系的 N 個星球，由編號1到N表示。
星球之間由 M 條雙向的道路相連，每條路連接恰好2個不同的星球。
首先，他必須透過議會以及政府對每個星球做約束。

兔王希望，每個星球與政府以及議會都不可以隔太遠，他希望可以滿足以下的條件：
1.每個星球可以設立一個議會，或者一個政府，或者可以都不設立，但是不可以兩者都設立。
2.每一個星球與政府以及議會都至少要相鄰，或者建立在該星球上。

由於兔王現在很忙，他決定請你幫他規劃出一個可行的方案。

Input：

第1行有兩個正整數N,M (N ≤ 200000; M ≤ 500000)。
接下來 M 行，每行有 2 個正整數A,B，代表A星球與B星球是相連的。

Output：

若存在一種滿足兔王要求的方案，第一行請輸出"TAK"。
接著 N 行，第 i+1 行可以輸出三種英文字母 K(建立議會)；S(建立政府)；N(什麼都不設置)，代表第 i 個星球的建設方案。

如果沒有解，第一行輸出"NIE"即可。

Sample Input：

7 8
1 2
3 4
5 4
6 4
7 4
5 6
5 7
6 7

Sample Output：

TAK
K
S
K
S
K
K
N

HINT：

範例輸出的圖形，圓圈代表議會(K)，菱形代表政府(S)，若都沒有代表不建設(N)。

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

#include<stdio.h>

#include<vector>

#include<string.h>

using namespace std;

vector<int> s[200005];

int visit[200005]={0},p[200005]={0},flag;

void dfs(int k,int l){

    int i,r;

    p[k]=l;

    for(i=0;i<s[k].size();i++){

        r=s[k][i];

        if(visit[r]==0){

            visit[r]=1;

            dfs(r,3-l);

        }

    }

}

int main(){

    int n,m,i,j,x,y;

    while(scanf("%d",&n)!=EOF && n){

        scanf("%d",&m);

        for(i=0;i<m;i++){

            scanf("%d%d",&x,&y);

            s[x].push_back(y);

            s[y].push_back(x);

        }

        for(i=1;i<=n;i++){

            if(visit[i]==0) dfs(i,1);

            if(s[i].size()==0){

                puts("NIE");

                return 0;

            }

        }

        puts("TAK");

        for(i=1;i<=n;i++)

            if(p[i]==1) puts("K");

            else puts("S");

    }

}