Cod sursa(job #542345)

Utilizator bora_marianBora marian bora_marian Data 26 februarie 2011 12:04:17
Problema Gossips Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 0.92 kb
#include<fstream>
#include<vector>
#define DIM 100004
using namespace std;
vector<int>G[DIM];
vector<int>K[DIM];
int N,M,Q,grad[DIM],t[DIM],a,b,rez;
void afla(int a,int b);
void dfs(int k);
int main()
{
	ifstream fin("gossips.in");
	ofstream fout("gossips.out");
	fin>>N>>M>>Q;
	int i,q;
	for(i=1;i<=M;i++)
	{
		fin>>a>>b;
		G[a].push_back(b);
		grad[b]++;
	}
	for(i=1;i<=N;i++)
	   if(grad[i]==0)
	      dfs(i);
	for(i=1;i<=Q;i++)
	{
		fin>>q>>a>>b;
		if(q==1)
		{
			rez=0;
			afla(a,b);
			if(rez==0)
			  fout<<"NO"<<"\n";
			else
			  fout<<"YES"<<"\n";
		  }
		  else
		     K[a].push_back(b);
     }
     return 0;
 }
void dfs(int k)
{
	for(int i=0;i<G[k].size();i++)
	   t[G[k][i]]=k,dfs(G[k][i]);
}
void afla(int a,int b)
{
	
	int aux;
	while(a!=0 && rez==0)
	{
		for(int i=0;i<K[a].size();i++)
		{
			aux=K[a][i];
			while(aux!=0 && rez==0)
			{
				if(aux==b)
				  rez=1;
				aux=t[aux];
			}
		}  
	  a=t[a];
	 }
}