本文共 820 字，大约阅读时间需要 2 分钟。

题意：给出一个图包括3∗n个点和m条边，一个边的集合定义如下，边的两端点只能属于一条边；一个点的集合定义如下：没有一条边把任意两个点连接。如果有这样的一个大小是n的边的集合，输出"Matching"和边按输入顺序的序号，如果有这样一个大小是n的点的集合，输出”IndSet“和点的序号，如果都没有，输出”Impossible“。（∑n≤1e5，∑m≤5e5）。 思路：这个思维也真的清奇，一开始疯狂想着是不是可以用并查集来解决，但复杂度都太大，结果一看题解才发现是水题（QAQ），我们可以枚举给出的m条边，暴力找一下是否存在数量大于等于n的边的集合，具体做法就是如果一条边的两边都没有被标记，说明这条边可以被加入集合，如果存在直接输出matching就可以了，那么如果不存在呢？这里就是考察思维的地方了，如果不存在，说明被边的集合数量小于n，被标记的点的数量小于2n，那么剩余的没有被标记的为3n-2*n一定大于n，而没有被标记的点一定满足点的集合的定义，直接输出就行，所以不存在没有答案的情况。

#include
   
    using namespace std;const int maxn=5e5+5;vector
    
     ans;int T,n,m,u,v,vis[maxn];int main(){
   	scanf("%d",&T);	while(T--)	{
   		ans.clear();		scanf("%d %d",&n,&m);		for(int i=0;i<=3*n+1;++i) vis[i]=0;		for(int i=1;i<=m;++i)		{
   			scanf("%d %d",&u,&v);			if(!vis[u]&&!vis[v])			{
   				vis[u]=vis[v]=1;				ans.push_back(i);			}		}		if(ans.size()
    
   

转载地址：http://fbign.baihongyu.com/