D. Relatively Prime Graph

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--D. Relatively Prime Graph

题解

中档题。题意大概是要求构成n个点m条边个图。图要求满足联通,每个边连接的两个点最大公约数为1,没有重边自环。
如果m<n-1图不联通,否则直接两重循环判断如果最大公约数为1则连接两点。

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
vector <pair<int, int>> v;
int n, m;
int main() {
    cin >> n >> m;
    if (m < n - 1) { 
        cout << "Impossible"; 
        return 0;
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1)v.push_back({ i,j });
            if (v.size() == m) {
                cout << "Possible" << endl;
                for (auto k : v) {
                    cout << k.first << ' ' << k.second << endl;
                }
                return 0;
            }
        }
    }
    cout << "Impossible";
}

标签: math, graphs, greedy

添加新评论