题解归档 - cf1198C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1198C
• 本地来源：problems/cf1198C/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/C
• 原始标题：1198C — Matching vs Independent Set

思路

1198C — Matching vs Independent Set

题意

给定 $3n$ 个顶点、$m$ 条边的无向图（多测）。求大小为 $n$ 的匹配（$n$ 条边两两不共享端点），或大小为 $n$ 的独立集（$n$ 个顶点两两无边）；否则输出 Impossible。

做法（贪心）

按输入顺序扫边：若端点 $u,v$ 都尚未被占用，则把该边加入匹配并标记 $u,v$。

• 若最终匹配边数 $\ge n$：输出前 $n$ 条边。
• 否则：所有未标记顶点构成独立集，且数量 $\ge n$（因为至多选了 $n-1$ 条边，占用 $<2n$ 个顶点，剩余 $>n$ 个）。输出前 $n$ 个未标记顶点。

正确性：贪心得到的匹配是极大匹配。若匹配不足 $n$，任意未标记顶点之间不可能有边（否则该边会被加入），故未标记点集为独立集；且 $3n-2(n-1)\ge n+2>n$。

复杂度

$O(n+m)$ 每组。

验证

• 官方样例通过（输出方案与标答不同但均合法）。
• stress.py -n 500：369 组连续 AC 后因 Kali SSH 中断；无 WA。

链接

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

代码

来源：problems/cf1198C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:17:36
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=3e5+5;
ll t,n,m,i,j,k,zc,pd,cur,cnt,ans;
ll used[maxn];
vector<ll>mtch;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        mtch.clear();
        for(i=1;i<=3*n;i++) used[i]=0;
        for(i=1;i<=m;i++){
            ll a,b;
            cin>>a>>b;
            if(!used[a] and !used[b]){
                used[a]=used[b]=1;
                mtch.push_back(i);
            }
        }
        if((ll)mtch.size()>=n){
            cout<<"Matching\n";
            for(i=0;i<n;i++){
                cout<<mtch[i];
                if(i+1<n) cout<<" ";
                else cout<<"\n";
            }
        }else{
            cout<<"IndSet\n";
            for(i=1;i<=n;i++){
                if(!used[i]) cout<<i;
                else if(!used[i+n]) cout<<i+n;
                else cout<<i+2*n;
                if(i<n) cout<<" ";
                else cout<<"\n";
            }
        }
    }
    return 0;
}