You are given a graph with 3⋅𝑛 vertices and 𝑚 edges. You are to find a matching of 𝑛 edges, or an independent set of 𝑛 vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

大致题意 📖

给你一张3n3*nmm边的简单图(不带重边与负环)
找出nn条独立边(匹配)或者点数为nn的独立点集

链接 🔗

「CodeForces 1198C」 Matching vs Independent Set

题解 ❓

先枚举,如果一条边E(x,y)E(x,y) 中的xxyy都没有出现过,那么该边绝对不会与前面的边有共同交点,因此该边属于匹配。
剩余没有被边覆盖的边一定为独立点,因为如果剩下的点Vi,VjV_i,V_j中存在E(Vi,Vj)E(V_i,V_j),那么一定会被选入到匹配中
如果匹配数kk大于nn则输出匹配,否则剩余点数为n2k>n(k<n)n - 2 * k > n (k< n)

代码

const ll maxd = 4e5+10;
int main()
{
//    __IN;__OUT;
    ll t;RLL(t);
    while(t--)
    {
        ll n,m,x,y;RLL2(n,m);
        V vis((3*n)+1,0),ans;
        F(m)
        {
            RLL2(x,y);
            if(!vis[x] && !vis[y])
            {
                vis[x] = vis[y] = 1;
                ans.pb(i+1);
            }
        }
 
        if(ans.size()>=n)
        {
            PS("Matching");
            ll tot = 0;
            for(auto x:ans) {
                PLP(x);tot++;
                if(tot == n) break;
            }
        }
        else
        {
            PS("IndSet");
            ll tot = 0;
            FOR(i,1,3*n)
                if(!vis[i])
                {
                    PLP(i);tot++;
                    if (tot == n) break;
                }
        }
        PN();
    }
    return 0;
}