题目链接：Codeforces 1199E

给定一个由 $3 \cdot n$ 个点、$m$ 条边组成的图。你需要找到一组大小为 $n$ 的边的匹配，或者找到一组大小为 $n$ 的独立集。

一组边的匹配表示不存在两条边拥有一个共同的点。

一组独立集表示不存在两个点被同一条边相连。

如果能找到一组边的匹配，输出 Matching 和方案；如果能找到一组独立集，输出 IndSet 和方案；否则输出 Impossible。

本题有 $T$ 组数据。

数据范围：$1 \le \sum n \le 10 ^ {5}$，$0 \le \sum m \le 5 \times 10 ^ {5}$。

Solution

首先考虑 $3 \cdot n$ 个点有什么性质？如果存在一组不小于 $n$ 的匹配，那么这组匹配一定对应着不小于 $2n$ 个点——找到一组匹配；如果在某一时刻，按顺序加入匹配时找不到下一个匹配而此时的匹配数量少于 $n$ 个，那么剩下的点一定多于 $n$ 个且两两没有边相连——找到一组独立集。

所以不存在无解情况。

时间复杂度：$\mathcal O(\sum n + \sum m)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5, M = 5e5 + 5;

int T, n, m, k;
bool dn[N], dm[M];

int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d%d", &k, &m), n = 3 * k;
        std::fill(dn + 1, dn + n + 1, false);
        std::fill(dm + 1, dm + m + 1, false);
        for (int i = 1, u, v; i <= m; i++) {
            scanf("%d%d", &u, &v);
            if (dn[u] || dn[v]) continue;
            dm[i] = dn[u] = dn[v] = true;
        }
        int cn = 0, cm = 0;
        for (int i = 1; i <= n; i++) cn += (dn[i] ? 0 : 1);
        for (int i = 1; i <= m; i++) cm += (dm[i] ? 1 : 0);
        if (cm >= k) {
            printf("Matching\n");
            for (int i = 1, cnt = 0; cnt < k; i++) {
                if (dm[i]) printf("%d%c", i, " \n"[++cnt == k]);
            }
        } else if (cn >= k) {
            printf("IndSet\n");
            for (int i = 1, cnt = 0; cnt < k; i++) {
                if (!dn[i]) printf("%d%c", i, " \n"[++cnt == k]);
            }
        } else {
            printf("Impossible\n");
        }
    }
    return 0;
}