题意:
要在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; }