首页 > ACM题库 > HDU-杭电 > hdu 3701 Country X待解决[解题报告]C++
2015
02-21

hdu 3701 Country X待解决[解题报告]C++

Country X

问题描述 :

Country X is a country with special structure.

1. It consists of N cities. The indices of the cities are from 0 to N – 1.
2. There are exact M roads between cities. A road is a bidirectional path that connects two different cities. There is at most one road between any two cities. There are no roads connect a city to itself.
3. You can travel from each city to any other cities using these roads. In other words, all the cities are in one connect component.
4. There is exact one special city called centre city X. When X is removed (the roads connect with X are also removed), the cities are partitioned into K parts. There are no roads between any two parts. For each part, you can travel from each city to any other cities in this part (each of the K parts is a connect component).
5. Most important of all, each of the K parts is identical to each other.

Now given N, M, and K, you are asked to construct a valid structure for Country X.

输入:

There are no more than 100 cases. For each case, there is only one line giving 3 integers N M K (2 <= N <= 500, 0 <= M <= 10000, 1 <= K <= N).

输出:

There are no more than 100 cases. For each case, there is only one line giving 3 integers N M K (2 <= N <= 500, 0 <= M <= 10000, 1 <= K <= N).

样例输入:

7 6 3
6 6 3

样例输出:

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


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。