Pagini recente » Cod sursa (job #2048320) | Cod sursa (job #1264646) | Cod sursa (job #2230158) | Cod sursa (job #2147045) | Cod sursa (job #542565)
Cod sursa(job #542565)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("gossips.in");
ofstream g("gossips.out");
struct nod
{ int father;
vector<int>out;
vector<int>goss;
};
int N,M,Q;
nod arb[100001];
queue<int>q;
queue<int>qq;
bool fin(int x,int y)
{ int i,j;
qq.push(y);
while(!qq.empty())
{ j=qq.front(); qq.pop();
for(i=0;i<arb[x].goss.size();i++)
if(arb[x].goss[i]==j)
return 1;
for(i=0;i<arb[j].out.size();i++)
qq.push(arb[j].out[i]);
}
return 0;
}
bool query(int x,int y)
{ int i,j; int fath;
q.push(x);
while(!q.empty())
{ i=q.front();q.pop();
if(fin(i,y))
return 1;
for(j=0;j<arb[i].out.size();j++)
q.push(arb[i].out[j]);
}
fath=x;
while(fath)
{ if(fin(fath,y))
return 1;
fath=arb[fath].father;
}
return 0;
}
int main()
{ int i,j,x,y,s;
f>>N>>M>>Q;
for(i=1;i<=M;i++)
{ f>>x>>y;
arb[x].out.push_back(y);
arb[y].father=x;
}
for(i=1;i<=Q;i++)
{ f>>s>>x>>y;
if(s==2)
arb[x].goss.push_back(y);
else
if(query(x,y)) g<<"YES"<<'\n';
else g<<"NO"<<'\n';
}
f.close();
g.close();
return 0;
}