Pagini recente » Profil lil_bloc | Cod sursa (job #2326567) | Cod sursa (job #1263553) | Cod sursa (job #2990136) | Cod sursa (job #542440)
Cod sursa(job #542440)
#include <iostream>
#include <fstream>
#include <vector>
#define DN 100005
using namespace std;
typedef vector<int>::iterator it;
int rang[DN],n,m,q,pr[DN];
vector<int> gr[DN],gt[DN];
ofstream g("gossips.out");
bool dfst(int sursa, int y) {
if(sursa==y) return 1;
for(;sursa!=pr[sursa];sursa=pr[sursa]) if(sursa==y) return 1;
if(sursa==y) return 1;
return 0;
}
bool dfs(int sursa,int y) {
if(sursa==y) return 1;
for(it j=gr[sursa].begin(); j!=gr[sursa].end(); ++j) if(dfst(*j,y)) return 1;
return 0;
}
void dfsa(int x,int y) {
for(it j=gt[x].begin(); j!=gt[x].end(); ++j) dfsa(*j,y);
gr[x].push_back(y);
}
int main()
{
ifstream f("gossips.in");
f>>n>>m>>q;
for(int i=1; i<=n; ++i) pr[i]=i;
for(int i=1; i<=m; ++i) {
int x,y;
f>>x>>y;
pr[y]=x;
gt[x].push_back(y);
}
for(int i=1; i<=q; ++i) {
int s,x,y;
f>>s>>x>>y;
if(1==s) {
if(dfs(x,y)) {
g<<"YES\n";
continue;
}
g<<"NO\n";
}else {
dfsa(x,y);
for(x=pr[x];x!=pr[x];x=pr[x]) gr[x].push_back(y);
gr[x].push_back(y);
}
}
/*for(int i=1; i<=n; ++i) {
cout<<i<<": ";
for(it j=gt[i].begin(); j!=gt[i].end();++j) cout<<*j<<' ';
cout<<endl;
}*/
return 0;
}