Codeforces 1199E-Matching vs Independent Set【思维】

题目链接

题意

给一个有3*n个点和m条边的一个无向图；
找出一个大小为n的边集，要求集合内没有两条边有共同的点，称为Matching；
输出Matching和n条边编号
或者找出一个大小为n的点集，要求集合内没有两个点有边相连，称为IndSet；
输出IndSet和n个点编号
如果没有就输出Impossible

思路

这题虽然放在E题但是其实就是个大水题，一条边要加到Matching里会消耗两个点，我们只需要把边遍历一遍，把没有使用过的点加入到集合里面，剩下的就是IndSet的点；因为如果剩下的点不是IndSet集合里的点，那就是Matching的；当Matching里的边大于n时我们就输出Matching，否则输出IndSet，所以其实所有的样例都是有可能的，不存在impossible；

代码

#include <bits/stdc++.h> 
const int maxn = 100100;

bool vis[3 * maxn];
vector<int> mat, ind;


int main(){
	int t, n, m, u, v;
	scanf("%d", &t);
	while(t--){
		while(!mat.empty()){
			mat.pop_back();
		}
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= 3 * n; i++){
			vis[i] = false;
		}
		for(int i = 1; i <= m; i++){
			scanf("%d%d", &u, &v); 
			if(!vis[u] && !vis[v]){
				vis[u] = true;
				vis[v] = true;
				mat.push_back(i);
			}
		}
		if(mat.size() >= n){
			printf("Matching\n");
			for(int i = 0; i < n; i++){
				printf("%d ", mat[i]);
			}
			printf("\n");
		}
		else{
			int i = 0, j = 1;
			printf("IndSet\n");
			while(i < n){
				if(!vis[j]){
					printf("%d ", j);
					i++;
				}
				j++;
			}
			cout << endl;
		}
	}
}