[BJOI 2018]染色

题意：求01成立。

并查集维护，记录一个变量判断决策。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 4000010;

int f[maxn];

inline int find(int x){

	return x == f[x]?x : f[x] = find(f[x]);

}

signed main()

{

	ios::sync_with_stdio(false);

	int T;

	cin >> T;

	while(T--){

		int n,m;

		cin >> n >> m;

		int tag = (m < n + 2);

		for(int i = 1;i <= (n << 1); ++i){

			f[i] = i;

		}

		for(int i = 1;i <= m; ++i){

			int x,y;

			cin >> x >> y;

			f[find(x)] = find(y + n);

			f[find(y)] = find(x + n);

		}

		for(int i = 1;i <= n && tag; ++i){

			tag &= (find(i) != find(i + n));

		}

		if(tag) puts("YES");

		else puts("NO");

	}

	return 0;

}

巴特西

[BJOI 2018]染色

最新文章

热门文章