Pagini recente » Cod sursa (job #2716035) | Cod sursa (job #994351) | Cod sursa (job #1378852) | Solutii Autumn Warmup, Runda 2 | Cod sursa (job #542404)
Cod sursa(job #542404)
#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, temp;
bool tre;
for(i = 1; i <= Q; i++)
{
scanf("%d %d %d",&op,&x,&y);
if(op == 1)
{
//grup = which[x];
if(exist(x, y))
printf("YES\n");
else printf("NO\n");
}
else
{
//grup = which[x];
if(!exist(x,y))
{
S.push(x);
mark = 0;
while(!S.empty())
{
temp = S.top();
S.pop();
tre = true;
for(it = G[temp].begin(); it < G[temp].end(); it++)
{
tre = false;
S.push(*it);
}
if(tre)
which[++mark] = temp;
}
}
do
{
for(grup = 1; grup <= mark; grup++)
if(!exist(which[grup],y))
{
temp = which[grup];
while(temp)
{
if(!exist(temp, y))
{
knows[temp].pb(y);
about[y].pb(temp);
}
else break;
temp = T[temp];
}
}
y = T[y];
} while(y);
}
}
return 0;
}