CF 1198C Matching vs Independent Set

题目描述

https://codeforces.com/problemset/problem/1198/C

Solution

CF 1440D Graph Subset Problem 虽然和这道题是同类型的，但是要简单的多

我们直接遍历所有边，维护一个边独立集

如果这个边独立集的大小大于等于 $n$，那么就直接输出这个边独立集

否则剩下的不在边独立集中的点的个数一定大于等于 $n$，且这些点一定没有边，否则他们就能加入边独立集

所以这时候直接输出剩下的点即可

#include <iostream>
#include <vector>
#define maxn 300010
using namespace std;

int n, m;

bool vis[maxn];
void work() {
    cin >> n >> m;
    for (int i = 1; i <= n * 3; ++i) vis[i] = 0;
    vector<int> ans;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        if (!vis[x] && !vis[y]) vis[x] = vis[y] = 1, ans.push_back(i); 
    }
    if (ans.size() >= n) {
        cout << "Matching\n";
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1]; 
    }
    else {
        cout << "IndSet\n";
        for (int i = 1, cnt = 0; i <= 3 * n && cnt < n; ++i)
            if (!vis[i]) cout << i << " \n"[++cnt == n]; 
    }
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0; 
}