Pagini recente » Cod sursa (job #719135) | Cod sursa (job #2717186) | Cod sursa (job #717676) | Cod sursa (job #2518678) | Cod sursa (job #542365)
Cod sursa(job #542365)
#include <stdio.h>
#include <vector>
#include <stack>
#include <iostream>
#define pb push_back
using namespace std;
int N, M, Q;
const int nmax = 100010;
int T[nmax], which[nmax];
vector<int> G[nmax];
vector<int> knows[nmax];
vector<int> about[nmax];
vector<int>::iterator it;
stack<int> S;
void read()
{
freopen ("gossips.in","r",stdin);
freopen ("gossips.out","w",stdout);
scanf("%d %d %d",&N,&M,&Q);
int a, b, i;
for(i = 1; i <= M; i++)
{
scanf("%d %d",&a,&b);
G[a].pb(b);
T[b] = a;
}
}
int mark;
void marque()
{
int i, x;
for(i = 1; i <= N; i++)
if(!T[i])
{
S.push(i);
which[i] = ++mark;
while(!S.empty())
{
x = S.top();
S.pop();
for(it = G[x].begin(); it < G[x].end(); it++)
{
which[*it] = mark;
S.push(*it);
}
}
}
}
bool exist(int grup, int y)
{
if(knows[grup].size() < about[y].size())
for(it = knows[grup].begin(); it < knows[grup].end(); it++)
{
if(*it == y)
return true;
}
else
{
for(it = about[y].begin(); it < about[y].end(); it++)
if(*it == grup)
return true;
}
return false;
}
int main()
{
read();
marque();
int i, x, y, op, grup;
for(i = 1; i <= Q; i++)
{
scanf("%d %d %d",&op,&x,&y);
if(op == 1)
{
grup = which[x];
if(exist(grup, y))
printf("YES\n");
else printf("NO\n");
}
else
{
grup = which[x];
do
{
if(exist(grup,y))
break;
knows[grup].pb(y);
about[y].pb(grup);
y = T[y];
} while(y);
}
}
return 0;
}