Problem B
Claw Decomposition

Input: Standard Input

Output: Standard Output

 

A claw is defined as a pointed curved nail on the end of each toe in birds, some reptiles, and some mammals. However, if you are a graph theory enthusiast, you may understand the following special class of graph as shown in the following figure by the word claw.

If you are more concerned about graph theory terminology, you may want to define claw as K_1,3.

 

Let’s leave the definition for the moment & come to the problem. You are given a simple undirected graph in which every vertex has degree 3. You are to figure out whether the graph can be decomposed into claws or not.

 

Just for the sake of clarity, a decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.

 

Input

 

There will be several cases in the input file. Each case starts with the number of vertices in the graph, V (4<=V<=300). This is followed by a list of edges. Every line in the list has two integers, a & b, the endpoints of an edge (1<=a,b<=V). The edge list ends with a line with a pair of 0. The end of input is denoted by a case with V=0. This case should not be processed.

 

Output

 

For every case in the input, print YES if the graph can be decomposed into claws & NO otherwise.

 

Sample Input                                                  Output for Sample Input

4 1 2 1 3 1 4 2 3 2 4 3 4 0 0 6 1 2 1 3 1 6 2 3 2 5 3 4 4 5 4 6 5 6 0 0 0

NO NO

---

題目是要檢查爪子, 但是爪子可能重疊在一起, 我們必須分解能不能都是爪子,
如此一來可以判定, 只要是二分圖就能拆成很多爪子, 但是一個圖形可以是很多二分圖,
因此要注意這一點。

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
bool checkBipartite(int V, vector<int> map[], bool color[], bool used[], int st) {
    queue<int> Q;
    Q.push(st);
    int tn;
    color[st] = true, used[st] = true;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(vector<int>::iterator i = map[tn].begin(); i != map[tn].end(); i++) {
            if(used[*i] == false) {
                used[*i] = true;
                color[*i] = !color[tn];
                Q.push(*i);
            } else {
                if(color[*i] == color[tn])
                    return false;
            }
        }
    }
    return true;
}
int main() {
    int V, x, y;
    vector<int> map[301];
    while(scanf("%d", &V) == 1 && V) {
        for(int i = 0; i <= V; i++)
            map[i].clear();
        while(scanf("%d %d", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            map[x].push_back(y);
            map[y].push_back(x);
        }
        bool color[V+1], used[V+1], ans = true;
        memset(color, 0, sizeof(color));
        memset(used, 0, sizeof(used));
        for(int i = 1; i <= V; i++) {
            if(used[i] == false) {
                ans &= checkBipartite(V, map, color, used, i);
            }
        }
        if(ans == true)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}