CodeForces 1009 D.Relatively Prime Graph(构造,gcd)

题意：

要求构造n个点m条边的连通图
满足，相连的点的gcd为1(互质)
如果可以，输出Possible和m条边的端点
如果不行，输出Impossible

思路：

首先要保证图连通，至少需要n-1条边，则如果m小于n-1，一定不可能

因为相邻的两个数互质，则可以先建立一条链(1->2,2->3,3->4)，一共n-1条边，这样就满足连通了。
然后不足m的边随便加加就行了，直接暴力就行(互质的数好多好多)。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+5;
vector<pair<int,int> >ans;
int n,m;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
signed main(){
cin>>n>>m;
if(n-1>m){
cout<<"Impossible"<<endl;
return 0;
}
for(int i=1;i<n;i++){
ans.push_back({i,i+1});
}
m-=n-1;
for(int i=1;i<=n&&m;i++){
for(int j=i+2;j<=n&&m;j++){
if(gcd(i,j)==1){
ans.push_back({i,j});
m--;
}
}
}
if(m){
cout<<"Impossible"<<endl;
return 0;
}
cout<<"Possible"<<endl;
for(auto i:ans){
cout<<i.first<<' '<<i.second<<endl;
}
return 0;
}

最后

以上就是顺心白羊为你收集整理的CodeForces 1009 D.Relatively Prime Graph(构造,gcd)的全部内容，希望文章能够帮你解决CodeForces 1009 D.Relatively Prime Graph(构造,gcd)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。