Cod sursa(job #542565)

Utilizator andunhillMacarescu Sebastian andunhill Data 26 februarie 2011 14:59:46
Problema Gossips Scor 20
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.11 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("gossips.in");
ofstream g("gossips.out");
struct nod
{	int father;
	vector<int>out;
	vector<int>goss;
};
int N,M,Q;
nod arb[100001];
queue<int>q;
queue<int>qq;
bool fin(int x,int y)
{	int i,j;
	qq.push(y);
	while(!qq.empty())
	{	j=qq.front(); qq.pop();
		for(i=0;i<arb[x].goss.size();i++)
			if(arb[x].goss[i]==j)
				return 1;
		for(i=0;i<arb[j].out.size();i++)
			qq.push(arb[j].out[i]);
	}
	return 0;
}
bool query(int x,int y)
{	int i,j; int fath;
	q.push(x);
	while(!q.empty())
	{	i=q.front();q.pop();
		if(fin(i,y))
			return 1;
		for(j=0;j<arb[i].out.size();j++)
			q.push(arb[i].out[j]);
	}
	fath=x;
	while(fath)
	{	if(fin(fath,y))
			return 1;
		fath=arb[fath].father;
	}
	return 0;
}
int main()
{	int i,j,x,y,s;
	f>>N>>M>>Q;
	for(i=1;i<=M;i++)
	{	f>>x>>y;
		arb[x].out.push_back(y);
		arb[y].father=x;
	}
	for(i=1;i<=Q;i++)
	{	f>>s>>x>>y;
		if(s==2)
			arb[x].goss.push_back(y);
		else
			if(query(x,y)) g<<"YES"<<'\n';
			else g<<"NO"<<'\n';
	}
	f.close();
	g.close();
	return 0;
}