题意:
要在N个城市之间修建道路,使得任意两个城市都可以到达,而且不超过两条路,还有,有些城市之间是不能修建道路的。
思路:
要将N个城市全部相连,刚开始以为是最小生成树的问题,其实就是一道简单的题目。 要求两个城市之间不超过两条道路,那么所有的城市应该是连在一个点上的,至于这个点就很好找了,只要找到一个没有和其他点有道路限制的即可。
//cf 192 B
#include <stdio.h>
#include <string.h>
char map[1005][1005];
int main()
{
int n, m;
while (scanf("%d %d", &n, &m) != EOF)
{
int s, e;
memset(map, 0, sizeof(map));
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &s, &e);
map[s][e] = 1;
map[e][s] = 1;
}
int x;
for (int i = 1; i <= n; i++)
{
int flag = 1;
for (int j = 1; j <= n; j++)
{
if (map[i][j])
{
flag = 0;
break;
}
}
if (flag)
{
x = i;
break;
}
}
printf("%d\n", n-1);
for (int i = 1; i <= n; i++)
{
if (x == i)
continue;
else
printf("%d %d\n", x, i);
}
}
return 0;
}