Pagini recente » Cod sursa (job #1840947) | Cod sursa (job #1963468) | nume | Cod sursa (job #485812) | Cod sursa (job #542458)
Cod sursa(job #542458)
#include <fstream>
using namespace std;
ifstream fin("gossips.in");
ofstream fout("gossips.out");
#include <vector>
#include <queue>
#define maxn 100005
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
int i,N,M,q,c,x,y,R;
vector <pair<int,int> > A[maxn];
vector <int> B[maxn];
queue<int> Q;
bool v[maxn];
int G[maxn];
void citire()
{
fin >> N >> M >> q;
for(i=1;i<=M;i++)
{
fin >> x >> y;
A[x].pb(mp(y,1));
A[y].pb(mp(x,0));
}
}
int verific(int x, int y)
{
vector<int> :: iterator it;
for(it=B[x].begin();it!=B[x].end();it++)
if(*it==y) return 1;
return 0;
}
void barfa()
{
int k;
vector <pair<int,int> > :: iterator it;
for(i=1;i<=G[0];i++) G[i]=0;
G[0]=0;
Q.push(x);
G[++G[0]]=x;
for(;!Q.empty();Q.pop())
{
k=Q.front();
for(it=A[k].begin();it!=A[k].end();it++)
if(!v[it->ff] && it->ss==0)
{
int nod=it->ff;
v[it->ff]=1;
Q.push(it->ff);
G[++G[0]]=it->ff;
}
}
for(i=1;i<=N;i++) v[i]=0;
Q.push(x);
for(;!Q.empty();Q.pop())
{
k=Q.front();
for(it=A[k].begin();it!=A[k].end();it++)
if(!v[it->ff] && it->ss==1)
{
v[it->ff]=1;
Q.push(it->ff);
G[++G[0]]=it->ff;
}
}
for(i=1;i<=N;i++) v[i]=0;
Q.push(y);
for(;!Q.empty();Q.pop())
{
k=Q.front();
for(i=1;i<=G[0];i++) B[G[i]].pb(k);
for(it=A[k].begin();it!=A[k].end();it++)
if(!v[it->ff] && it->ss==0)
{
v[it->ff]=1;
Q.push(it->ff);
}
}
}
int main()
{
citire();
for(;q;q--)
{
fin >> c >> x >> y;
for(i=1;i<=N;i++) v[i]=0;
while(!Q.empty()) Q.pop();
if(c==1)
{
R=verific(x,y);
if(R) fout << "YES";
else fout << "NO";
fout << '\n';
}
if(c==2)
barfa();
}
}