Cod sursa(job #542364)

Utilizator cdascaluDascalu Cristian cdascalu Data 26 februarie 2011 12:31:14
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.27 kb
#include<fstream>
#define MAX 15001
using namespace std;
struct graf
{
	int x;
	graf*next;
}*GRAF[MAX],*q;
int N,M,Q,V[MAX],nr_conexe,CONEX[15000][MAX],T[MAX];
char MAT[MAX][MAX];
//V[i] - carei componenta conexa apartine nodul i
void add(int x,int y)
{
	q = new graf;
	q->x = y;
	q->next = GRAF[x];
	GRAF[x] = q;
}
void bf(int x)
{
	int C[MAX],p,u,nod;
	p = u = 1;
	C[p] = x;
	V[x] = nr_conexe;
	CONEX[nr_conexe][1] = x;
	while(p<=u)
	{
		nod = C[p];
		q = GRAF[nod];
		while(q)
		{
			if(!V[q->x])
			{
				C[++u] = q->x;
				V[q->x] = nr_conexe;
				CONEX[nr_conexe][u] = q->x;
			}
			q = q->next;
		}
		++p;
	}
	CONEX[nr_conexe][0] = u;
}
int main()
{
	ifstream f("gossips.in");
	f>>N>>M>>Q;
	int x,y,c;
	while(M--)
	{
		f>>x>>y;
		add(x,y);
		add(y,x);
		//add1(x,y);
		T[y] = x;
	}
	for(x=1;x<=N;++x)
		if(!V[x])
		{
			++nr_conexe;
			bf(x);
		}
	ofstream g("gossips.out");
	int i,con,init;
	while(Q--)
	{
		f>>c>>x>>y;
		if(c == 1)
		{
			if(MAT[x][y])g<<"YES\n";
			else g<<"NO\n";
		}
		else
		{
			con = V[x];
			init = y;
			for(i = 1;i<=CONEX[con][0];++i)
			{
				y = init;
				while(y)
				{
					MAT[ CONEX[con][i] ][y] = 1;
					y = T[y];
				}
			}
		}
	}
	f.close();
	g.close();
	return 0;
}