Pagini recente » Statistici Titus-Teodor Pirsan (Titus_Pirsan) | Cod sursa (job #2181089) | Cod sursa (job #2200866) | Cod sursa (job #299741) | Cod sursa (job #542364)
Cod sursa(job #542364)
#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;
}