Решение задачи Строим дорогу с Codeforces

Без пояснения   Просмотров: 161

В одной стране есть n городов. Изначально в этой стране нет дорог. Но вот, однажды король решает построить дороги, соединяющие пары городов. По дорогам можно путешествовать в любую сторону. Король хочет построить дороги так, чтобы можно было добраться из любого города в любой другой, проехав не более двух дорог. Также дано m пар городов — между этими парами городов дороги строить нельзя.

Ваша задача — построить как можно меньше дорог так, чтобы вышеперечисленные условия выполнялись. Ограничения гарантируют, что это возможно всегда.

Код 

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli arr[1005]={0};
int main(void){
	lli n,m,a,b;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		arr[a] = 1;
		arr[b] = 1;
	}
	lli key;
	for(int i=1;i<=n;i++){
		if(arr[i] == 0){
			key = i;
			break;
		}
	}

	cout<<n-1<<endl;
	for(int i=1;i<=n;i++){
		if(i != key){
			cout<<i<<" "<<key<<endl;
		}
	}
return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 mycod   [email protected]  Карта сайта   Правообладателям