Cod sursa(job #542461)

Utilizator ConsstantinTabacu Raul Consstantin Data 26 februarie 2011 13:55:52
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.07 kb
#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;

vector<int> fii[ Nmax ],g[ Nmax ];
int tt[ Nmax ];
bool ok;

int n,m,q,a,b;

bool check(int a,int b){
int N,i,x,p;
N = g[a].size();

for(i = 0 ; i < N ; i++)
	{x  = g[a][i];
	for(p =x;p;p=tt[p])
		if(p==b)
			return true;
	}
return false;
}

void dfs(int nod,int b){
int N,i,x;
N = fii[nod].size();
if(check(nod,b)){
	ok = true;
	return ;
	}
for(i = 0 ; i <  N ;i++)
	{x = fii[nod][i];
	if(!ok)
		dfs(x,b);
	}
}

void citire(){
freopen("gossips.in","r",stdin);
freopen("gossips.out","w",stdout);
int q;
scanf("%d %d %d",&n,&m,&q);
int i,a,b,t;
for(i = 1 ; i <= m; i++)
	{scanf("%d %d",&a,&b);
	fii[a].push_back(b);
	tt[b] = a;
	}
	
int p ;

for(i = 1 ; i <= q; i++)
	{scanf("%d %d %d",&t,&a,&b);
	if(t == 2) 
		g[a].push_back(b);
	else
		{ok = false;
		dfs(a,b);
		for(p =tt[a];p;p = tt[p])
			if(check(p,b)){
				ok = true;
				break;
			}
		if(ok)
			printf("YES\n");
		else
			printf("NO\n");}
	}
}
int main(){
citire();
return 0;
}