首页 > ACM题库 > HDU-杭电 > hdu 4615 Play with Sequence待解决[解题报告]C++
2015
09-17

hdu 4615 Play with Sequence待解决[解题报告]C++

Play with Sequence

问题描述 :

  ivankevin loves sequences.
  A sequence of n elements is called a SWITCH SEQUENCE iff:
  Each element is a 2-switch, where a 2-switch is the replacement of a pair of edges xy & zw in a simple graph by the edges yz and wx, given that yz and wx did not appear in the graph originally.
  Now give two simple graphs G and H with same vertex set V, ivankevin wants to know whether there is a switch sequence transforms G into H.

输入:

  There are multiple test cases.
  Each case contains 1 + 2n lines. The positive integer n(0<n<101) is given in the first line. The next 2n lines are the matrix which describe the two graphs G and H. The j elements in the i rows is either 0 or 1. If the node i and the node j has a edge in the graph. The elements will be 1. Otherwise is 0. It’s guaranteed that the matrix is symmetry and the i elements in the i row is always 0. See sample input for more details.

输出:

  There are multiple test cases.
  Each case contains 1 + 2n lines. The positive integer n(0<n<101) is given in the first line. The next 2n lines are the matrix which describe the two graphs G and H. The j elements in the i rows is either 0 or 1. If the node i and the node j has a edge in the graph. The elements will be 1. Otherwise is 0. It’s guaranteed that the matrix is symmetry and the i elements in the i row is always 0. See sample input for more details.

样例输入:

4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0

样例输出:

1
0 1 3 2
-1