FZU 2192 位置信息挖掘 (并查集或暴力)

思路:将城市一样,并且相互未知的联一条边.

然后对每一个已知的城市进行遍历,将和他相同的点,并且是未知的,变成已知.

跑多次.直到不再增加新点为止.

#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define MAX 210000
int head[MAX<<1];
int r[MAX];
int s[MAX];
bool vis[MAX<<1];
int cnt;
struct edge
{
	int v;
	int next;
}edg[MAX<<2];
void init()
{
	cnt = 0;
	memset(head,-1,sizeof head);
	memset(r,sizeof r);
	memset(s,sizeof s);
}

void addedge(int u,int v)
{
	edg[cnt].v = v;
	edg[cnt].next = head[u];
	head[u] = cnt++;
}

int main()
{
	int n,m,q;
	while (~scanf("%d%d%d",&n,&m,&q))
	{
		int id,tg;
		init();
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d",&id,&tg);
			s[id] = tg;
		}
		int aa,aaa,aaaa;
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&aa,&aaa,&aaaa);
			if (aaaa)
				r[aa] = aaaa;
			if (s[aaa])
			{
				r[aa] = s[aaa];
			}
			else
			if (r[aa])
				s[aaa] = r[aa];
			else
			{
				addedge(aaa,aa + n);
				addedge(aa + n,aaa);
			}
		}
		int cnt = 0;
		int pre = -1;
		memset(vis,sizeof vis);
		while (cnt !=pre)
		{
			pre = cnt;
			for (int i = 1; i <= n;i++)
			if (s[i])
			{
				if (!vis[i])
				{
					vis[i] = 1;
					cnt++;
				}
				for (int j = head[i]; j != -1;j = edg[j].next)
				{
					r[edg[j].v-n] = s[i];
					if (!vis[edg[j].v])
					{
						vis[edg[j].v] = 1;
						cnt++;
					}
				}
			}
			for (int i = 1; i <= m;i++)
			if (r[i])
			{
				if (!vis[n+i])
				{
					vis[n+i] = 1;
					cnt++;
				}
				for (int j = head[n+i]; j != -1; j = edg[j].next)
				{
					s[edg[j].v] = r[i];
					if (!vis[edg[j].v])
					{
						vis[edg[j].v] = 1;
						cnt++;
					}
				}
			}
		}
		while (q--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			if (u == 0)
				printf("%dn",s[v]);
			else
				printf("%dn",r[v]);
		}
	}
}