Cod sursa(job #542549)

Utilizator robigiirimias robert robigi Data 26 februarie 2011 14:51:44
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.24 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

FILE *f=fopen("gossips.in", "r");
FILE *g=fopen("gossips.out", "w");

int n, m, q;

typedef struct nod
{
	int x;
	struct nod *adr;
};

nod *ls[100001];
nod *lj[100001];

int viz[100001];
int ok;
int v[3001][3001];

void add1(int x, int y)
{
	if (ls[y]==NULL)
	{
		ls[y]=new nod;
		ls[y]->x=x;
		ls[y]->adr=NULL;
	}
	else
	{
		nod *q=new nod;
		q->x=x;
		q->adr=ls[y];
		ls[y]=q;
	}
}

void add2(int x, int y)
{
	if (lj[x]==NULL)
	{
		lj[x]=new nod;
		lj[x]->x=y;
		lj[x]->adr=NULL;
	}
	else
	{
		nod *q=new nod;
		q->x=y;
		q->adr=lj[x];
		lj[x]=q;
	}
}
	
	


void read()
{
	fscanf(f, "%d%d%d", &n, &m, &q);
	
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add1(x, y);
		add2(x, y);
	}
}

void dfss(int x, int y, int ix)
{
	viz[x]=1;
	nod *p=ls[x];
	while (p!=NULL)
	{
		if (!viz[p->x])
		{
			if (p->x==y && (ix==1 && v[x][p->x]==0 || v[x][p->x]==1 && ix==0))
			{			
				ok=1;
				x=0;
				p=new nod;
				return ;
			}
			if (ix==0)
			{
				if (v[x][p->x]==1)
					dfss(p->x, y, 1);
				else dfss(p->x, y, 0);
			}
			else
				if (v[x][p->x]==0)
					dfss(p->x, y, 1);
		}
		p=p->adr;
	}
}

void dfsj(int x, int y, int ix)
{
	viz[x]=1;
	nod *p=lj[x];
	while (p!=NULL)
	{
		if (!viz[p->x])
		{
			if (p->x==y && (ix==1 && v[x][p->x]==0 || v[x][p->x]==1 && ix==0))
			{	
				ok=1;
				x=0;
				p=new nod;
				return ;
			}
			if (v[x][p->x]==1 && ix==0)
				dfss(p->x, y, 1);
			else
			{
				if (ix==0)
				{
					dfsj(p->x, y, 0);
				}
				else
					if (v[x][p->x]==0)
						dfsj(p->x, y, 1);
			}
		}
		p=p->adr;
	}
}


void program()
{
	for (int i=1; i<=q; ++i)
	{
		int s, x, y;
		fscanf(f, "%d%d%d", &s, &x, &y);
		if (s==2)
		{
			add1(y, x);
			add2(x, y);
			v[x][y]=1;
		}
		else
		{
			ok=0;
			memset(viz, 0, 4*n+4);
			dfss(x, y, 0);
			if (ok==1) fprintf(g, "YES\n");
			else
			{
				ok=0;
				memset(viz, 0, 4*n+4);
				dfsj(x, y, 0);
				if (ok==1) fprintf(g, "YES\n");
				else fprintf(g, "NO\n");
			}
		}
	}
}
	

int main()
{
	read();
	
	program();
	
	fclose(f);
	fclose(g);
	
	return 0;
}