admin管理员组文章数量:1602098
B. Road Construction
time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard outputA country has n cities. Initially, there is no road in the country. One day, the king decides to construct some roads connecting pairs of cities. Roads can be traversed either way. He wants those roads to be constructed in such a way that it is possible to go from each city to any other city by traversing at most two roads. You are also givenm pairs of cities — roads cannot be constructed between these pairs of cities.
Your task is to construct the minimum number of roads that still satisfy the above conditions. The constraints will guarantee that this is always possible.
InputThe first line consists of two integers n andm .
Then m lines follow, each consisting of two integersai andbi (1 ≤ ai, bi ≤ n,ai ≠ bi), which means that it is not possible to construct a road connecting citiesai andbi. Consider the cities are numbered from 1 ton.
It is guaranteed that every pair of cities will appear at most once in the input.
OutputYou should print an integer s: the minimum number of roads that should be constructed, in the first line. Thens lines should follow, each consisting of two integersai andbi (1 ≤ ai, bi ≤ n, ai ≠ bi), which means that a road should be constructed between cities ai and bi.
If there are several solutions, you may print any of them.
Sample test(s) Input4 1 1 3Output
3 1 2 4 2 2 3Note
This is one possible solution of the example:
These are examples of wrong solutions:
找到一条未出现的城市,然后以它为中心逐个建边就行了,一共n-1条边
#include<stdio.h>
#include<math.h>
#include<string.h>
#define N 1010
int main()
{
int i,n,m,a[N];
while(scanf("%d%d",&n,&m)!=EOF)
{
m*=2;
memset(a,0,sizeof(a));
while(m--)
{
scanf("%d",&i);
a[i]=1;
}
for(i=1;i<=n;i++)
if(!a[i])
break;
printf("%d\n",n-1);
for(m=1;m<=n;m++)
if(m!=i)
printf("%d %d\n",i,m);
}
return 0;
}
本文标签: codeforceRoadconstruction
版权声明:本文标题:codeforceB. Road Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728397280a1157154.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论