【BZOJ4195】【NOI2015】程序自动分析（并查集）

题面

Description

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3,...xn代表程序中出现的变量，给定n个形如xi=xj或者xi!=xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述条件同时被满足。

Input

第一行包含一个正整数t,表示需要判定的问题个数。注意这些问题之间相互独立。

对于每个问题，包含若干行：

第一行一个正整数n,表示约束条件个数。

接下来n行，每行三个正整数i,j,e,描述一个相等/不等的约束条件。若e=1,则约束条件为xi=xj，若e=0,则约束条件为xi!=xj

Output

输出包括T行。

输出的第k行输出一个字符串"YES"或者"NO"(不包含引号，字母全部大写).

Sample Input

输入样例1：

2

2

1 2 1

1 2 0

2

1 2 1

2 1 1

输入样例2：

2

3

1 2 1

2 3 1

3 1 1

4

1 2 1

2 3 1

3 4 1

1 4 0

Sample Output

输出样例1：

NO

YES

输出样例2：

YES

NO

题解

并查集傻逼题

至于编号怎么搞

离散一下就行了

离散怎么搞？

开个\(map\)就可以了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 110000

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int f[MAX<<4],n,tot;

map<int,int> M;

int Ret(int x)

{

	if(M.find(x)!=M.end())return M[x];

	M[x]=++tot;

	return tot;

}

int getf(int x)

{

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

}

struct Ask

{

	int u,v,e;

}a[MAX];

int main()

{

	int T=read();

	while(T--)

	{

		bool fl=true;

		n=read();M.clear();tot=0;

		for(int i=1;i<=n*2;++i)f[i]=i;

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

		{

			int u,v;

			u=a[i].u=read();

			v=a[i].v=read();

			a[i].e=read();

			u=Ret(u);v=Ret(v);

			if(a[i].e)//xi=xj

			{

				u=getf(u);v=getf(v);

				f[u]=v;

			}

		}

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

		{

			if(!a[i].e)

			{

				int u=Ret(a[i].u),v=Ret(a[i].v);

				if(getf(u)==getf(v))

				{

					fl=false;

					break;

				}

			}

		}

		fl?puts("YES"):puts("NO");

	}

	return 0;

}