The Door Problem

wjh15101051's space

卧薪尝胆，厚积薄发。

The Door Problem

Date: Mon Nov 05 18:33:51 CST 2018

In Category: NoCategory

Description：

有 $n$ 扇门， $m$ 个钥匙，每个钥匙会使一些特定的门改变状态，每扇门都由两个钥匙控制，问能否使得所有门都打开。

$1\leqslant n\leqslant 10^5$

Solution：

发现控制同一扇门地两个钥匙之间有要么一个用一个不用，要么两个都用或都不用的关系，这就是一个 $2-SAT$ 的模型，但是写着写着就会发现这个建的边是双向的，于是一个并查集就好了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

int s[MAXN];

vector<int> v[MAXN];

int id(int k,int x){return (k - 1) * 2 + x;}

int f[MAXN];

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

void merge(int a,int b)

{

	int p = find(a),q = find(b);

	if(p == q)return;

	f[p] = q;

	return;

} 

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&s[i]);

	int w,k;

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

	{

		f[id(i,0)] = id(i,0);

		f[id(i,1)] = id(i,1);

		scanf("%d",&w);

		for(int j = 1;j <= w;++j)

		{

			scanf("%d",&k);

			v[k].push_back(i);

		}

	}

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

	{

		merge(id(v[i][0],1),id(v[i][1],0 ^ s[i]));

		merge(id(v[i][0],0),id(v[i][1],1 ^ s[i]));

	}

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

	{

		if(find(id(i,0)) == find(id(i,1)))

		{

			puts("NO");

			return 0;

		}

	}

	puts("YES");

	return 0;

}

In tag: 图论-连通性-2-SAT 数据结构-并查集

wjh15101051