Cod sursa(job #542353)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 26 februarie 2011 12:15:46
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 0.96 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> V[100010];
void read(),solve();
int n,m,q,dad[100010],DAD[100010],calc(int),a,b,i,t,x,y,ok;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
}
void solve()
{
	for(;m;m--)
	{
		scanf("%d%d",&a,&b);
		dad[b]=a;
	}
	for(i=1;i<=n;i++)
		if(!dad[i])dad[i]=i;
	for(i=1;i<=n;i++)
	{
		if(dad[i]==i)DAD[i]=i;
		else DAD[i]=calc(dad[i]);
	}
	for(;q;q--)
	{
		scanf("%d%d%d",&t,&x,&y);
		if(t==2)
		{
			V[DAD[x]].push_back(y);
			for(;y!=dad[y];)
			{
				y=dad[y];
				V[DAD[x]].push_back(y);
			}
			continue;
		}
		ok=0;
		for(vector<int>::iterator it=V[DAD[x]].begin();it!=V[DAD[x]].end();it++)
			if(*it==y){ok=1;break;}
		if(ok)printf("YES\n");else printf("NO\n");
	}
}
int calc(int X)
{
	if(X==dad[X])return X;
	else 
	{
		X=dad[X];
		return calc(X);
	}
}