首页 > ACM题库 > HDU-杭电 > hdu 2975 Find a Minor待解决[解题报告]C++
2014
02-24

hdu 2975 Find a Minor待解决[解题报告]C++

Find a Minor

问题描述 :

In a graph G , contraction of an edge e with endpoints u , v is the replacement of u and v with a single vertex such that edges incident to the new vertex are the edges other than e that were incident with u or v . The resulting graph has one less edge than G . A graph H is a minor of a graph G if a copy of H can be obtained from G via repeated edge deletion, edge contraction and isolated node deletion.

Minors play an important role in graph theory. For example, every non-planar graph contains either the graph K3, 3 (i.e., the complete bipartite graph on two sets of three vertices) or the complete graph K5 as a graph minor.

Write a program to find a graph minor Kn, m or Kn in an undirected connected simple graph.

输入:

The input consists of several test cases. The first line of each case contains an integers V (3<=V<=12) , the number of vertices in the graph, followed by a string in format “Kn " or “Kn ,m " (1<=n, m<=V) , the graph minor you’re finding. The following V lines contain the adjacency matrix of the graph (1 means directly connected, 0 means not directly connected).

The diagonal elements of the matrix will always be 0, and the element in row i column j is always equal to the element in row j column i . The last test case is followed by a single zero, which should not be processed.

输出:

The input consists of several test cases. The first line of each case contains an integers V (3<=V<=12) , the number of vertices in the graph, followed by a string in format “Kn " or “Kn ,m " (1<=n, m<=V) , the graph minor you’re finding. The following V lines contain the adjacency matrix of the graph (1 means directly connected, 0 means not directly connected).

The diagonal elements of the matrix will always be 0, and the element in row i column j is always equal to the element in row j column i . The last test case is followed by a single zero, which should not be processed.

样例输入:

5 K2,2 
0 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
4 K3 
0 1 0 1 
1 0 1 0 
0 1 0 1 
1 0 1 0 
4 K2,2 
0 1 0 1 
1 0 1 1 
0 1 0 1 
1 1 1 0 
5 K2,2 
0 1 0 0 1
1 0 0 0 1
0 0 0 1 1
0 0 1 0 1
1 1 1 1 0
5 K4 
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0
0

样例输出:

Case 1: Not found 
Case 2: Found 
Case 3: Found 
Case 4: Not found 
Case 5: Found


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。