图论trainning-part-2 B. Claw Decomposition
B. Claw Decomposition
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 K1,3.
Lets 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 |
Problemsetter: Mohammad Mahmudur Rahman
Special Thanks to: Manzurur Rahman Khan
解题:二分图的判断,使用染色法!如果相邻顶点颜色相同,即不是二分图。
DFS解法
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #define LL long long 13 #define INF 0x3f3f3f3f 14 using namespace std; 15 const int maxv = 310; 16 struct arc{ 17 int v; 18 }; 19 vector<arc>g[maxv]; 20 int n; 21 bool color[maxv]; 22 bool dfs(int u){ 23 for(int i = 0; i < g[u].size(); i++){ 24 int j = g[u][i].v; 25 if(!color[j]){ 26 color[j] = !color[u]; 27 if(!dfs(j)) return false; 28 }else if(color[j] == color[u]) return false; 29 } 30 return true; 31 } 32 int main() { 33 int i,u,v; 34 while(scanf("%d",&n),n){ 35 if(n == 1) {puts("NO");continue;} 36 for(i = 1; i <= n; i++) 37 g[i].clear(); 38 while(scanf("%d%d",&u,&v),u||v){ 39 g[u].push_back((arc){v}); 40 g[v].push_back((arc){u}); 41 } 42 memset(color,false,sizeof(color)); 43 dfs(1)?puts("YES"):puts("NO"); 44 } 45 return 0; 46 }
BFS解法:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #define LL long long 13 #define INF 0x3f3f3f3f 14 using namespace std; 15 const int maxn = 310; 16 vector<int>g[maxn]; 17 queue<int>qu; 18 int n,color[maxn]; 19 bool bfs(int src){ 20 while(!qu.empty()) qu.pop(); 21 qu.push(src); 22 color[src] = 1; 23 while(!qu.empty()){ 24 int u = qu.front(),v; 25 qu.pop(); 26 for(int i = 0; i < g[u].size(); i++){ 27 v = g[u][i]; 28 if(color[v] == -1){ 29 color[v] = !color[u]; 30 qu.push(v); 31 }else if(color[v] == color[u]) return false; 32 } 33 } 34 return true; 35 } 36 int main(){ 37 int u,v; 38 while(scanf("%d",&n),n){ 39 memset(color,-1,sizeof(color)); 40 for(int i = 1; i <= n; i++) 41 g[i].clear(); 42 while(scanf("%d%d",&u,&v),u||v){ 43 g[u].push_back(v); 44 g[v].push_back(u); 45 } 46 bfs(1)?puts("YES"):puts("NO"); 47 } 48 return 0; 49 }
相关文章
- 【Mysql sql inject】【入门篇】SQLi-Labs使用 part 2【12-14】
- SpringBoot上传时出现异常 Required request part 'file' is not present
- [AWS - DA] Lambda (ALB, Mult-values header, Edge, Async invocation, Event Source Mapping, Destination) PART 1
- [Cloud DA] Serverless Framework with AWS - Part 1: DynamoDB & ApiGateway
- 【译】UNIVERSAL IMAGE LOADER.PART 2---ImageLoaderConfiguration详解
- Smart Template component rendering process - part 2
- 【华为云技术分享】“技术-经济范式”视角下的开源软件演进剖析-part 3
- Inside look at modern web browser (part 3)
- Inside look at modern web browser (part 1)
- Building Microservices with Spring Boot and Apache Thrift. Part 1 with servlet
- SharePoint Web Part Error – The Specified Solution Was Not Found
- wukong引擎源码分析之索引——part 3 文档评分 无非就是将docid对应的fields信息存储起来,为搜索结果rank评分用
- Oracle 技能强化 Part 7 日期运算
- Oracle 技能强化 Part 6 使用数字
- [ MySQL ] 使用Navicat进行MySQL数据库备份 / 还原(Part 1:备份.nb3文件方式)