Pagini recente » Cod sursa (job #2836218) | Cod sursa (job #2636842) | Cod sursa (job #1767486) | Cod sursa (job #2215734) | Cod sursa (job #542369)
Cod sursa(job #542369)
#include <iostream>
#include <fstream>
#include <vector>
#define DN 100005
using namespace std;
typedef vector<int>::iterator it;
int rang[DN],pre[DN],n,m,q,pr[DN];
vector<int> gr[DN];
int find(int el) {
int i,j;
for(i=el;i!=pre[i];i=pre[i]);
for(;el!=pre[el];) {
j=pre[el];
pre[el]=i;
el=j;
}
return i;
}
void re(int x, int y) {
if(rang[x]>rang[y]) pre[y]=x;
else pre[x]=y;
if(rang[x]==rang[y]) ++rang[y];
}
bool dfs(int sursa,int y) {
if(sursa==y) return 1;
if(pr[sursa]!=sursa)return dfs(pr[sursa],y);
return 0;
}
int main()
{
ifstream f("gossips.in");
ofstream g("gossips.out");
f>>n>>m>>q;
for(int i=1; i<=n; ++i) {
rang[i]=1;
pre[i]=pr[i]=i;
}
for(int i=1; i<=m; ++i) {
int x,y;
f>>x>>y;
pr[y]=x;
re(find(x),find(y));
}
for(int i=1; i<=q; ++i) {
int s,x,y;
f>>s>>x>>y;
if(1==s) {
if(x==y || find(x)==find(y)) {
g<<"YES\n";
continue;
}
bool ok=1;
x=find(x);
for(it j=gr[x].begin(); j!=gr[x].end(); ++j)
if(*j==y || dfs(*j,y)) {
g<<"YES\n";
ok=0;
break;
}
if(ok) g<<"NO\n";
}else
gr[find(x)].push_back(y);
}
return 0;
}