链接:Click here
题目意思：给你一个图，有3n个点，m条边，求是否有n条匹配边或n个独立点，其中匹配为没有公共点，独立为不相连
Solution：
考虑每个点对于第一种情况，最多只能贡献一次，所以先乱连，看能否达成条件
考虑无法达成条件，则此时被边相连的点不到2n个，还剩下大于n个点不相连，则必然满足有n个点独立
Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,tot;
int l[N],vis[N*3];
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
void solve(){n=read(),m=read();tot=0;for(int i=1;i<=3*n;i++) vis[i]=0;for(int i=1;i<=m;i++){int x=read(),y=read();if(!vis[x]&&!vis[y]){vis[x]=vis[y]=1;l[++tot]=i;}}if(tot>=n){puts("Matching");for(int i=1;i<=n;i++)printf("%d ",l[i]);return puts(""),void();}int num=0;puts("IndSet");for(int i=1;i<=3*n;i++){if(!vis[i]) printf("%d ",i),++num;if(num==n) return puts(""),void();}
}
int main(){int t=read();while(t--) solve();return 0;
}