UVA 11396：Claw Decomposition(二分图判定)

UVA 11396：Claw Decomposition(二分图判定)

问题描述：

A claw is defined as a pointed curved nail on the end of each toe in birds, somereptiles, and some mammals. However, if you are a graph theory enthusiast, youmay understand the following special class of graph as shown in the followingfigure by the word claw.If you are more concerned about graph theory terminology, you may want todefine claw as K1,3.Lets leave the definition for the moment and come to the problem. You aregiven a simple undirected graph in which every vertex has degree 3. You are tofigure 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 edgeappears 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 and b,the endpoints of an edge (1 ≤ a, b ≤ V ). The edge list ends with a line with a pair of ‘0’. The end ofinput 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 and ‘NO’ otherwise.

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

Sample Output

NO

NO

如果想明白这道题目仅仅只是判断是否是一个二分图的话就简单多了，判断二分图可以使用染色法，也就是找一个点，把它染成黑色，然后把它临接的点都染成白色，让相邻两个点的颜色不一样，如果可以成功染色，则是二分图，否则不是二分图。

AC代码：

#include#include#include#include#include#includeusing namespace std;int mapp[500][500];int vis[500],n;bool dfs(){ queueq; memset(vis,0,sizeof(vis)); q.push(0); vis[0]=1; while(!q.empty()) { int p=q.front(); q.pop(); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。