Pagini recente » Cod sursa (job #2386995) | Cod sursa (job #2972943) | Cod sursa (job #2584757) | Cod sursa (job #2449228) | Cod sursa (job #542534)
Cod sursa(job #542534)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct cp2{int x, y;} TT[100100];
struct cp3{bool b[100100];};
int RG[100100];
int j,r,ss,con,n, m,q,x,y,i;
int v[100100];
typedef bool bf[100100];
vector <cp3> S;
cp3 bif;
int find(int x)
{
int R, y;
//merg in sus pe arbore pana gasesc un nod care pointeaza catre el insusi
for (R = x; TT[R].x != R; R = TT[R].x);
//aplic compresia drumurilor
for (; TT[x].x != x;)
{
y = TT[x].x;
TT[x].x = R;
x = y;
}
return R;
}
void unite(int x, int y)
{
//unesc multimea cu rang mai mic de cea cu rang mai mare
if (RG[x] > RG[y])
TT[y].x = x;
else TT[x].x = y;
//in caz ca rangurile erau egale atunci cresc rangul noii multimi cu 1
if (RG[x] == RG[y]) RG[y]++;
}
bool cmp(cp2 i, cp2 j) {
return(i.x<j.x);
}
bool cmp2(cp2 i, cp2 j) {
return (i.y<j.y);
}
void bv(int y, int r) {
S[r].b[y]=true;
if (v[y]) {
if (S[r].b[v[y]]==false)
bv(v[y],r);
}
}
int main() {
f=fopen("gossips.in","r");
g=fopen("gossips.out","w");
fscanf(f,"%d%d%d",&n,&m,&q);
for (i = 1; i <= n; i++) {
TT[i].x = i;
TT[i].y = i;
RG[i] = 1;
}
for (i=1;i<=m;i++) {
fscanf(f,"%d%d",&x,&y);
unite(find(x), find(y));
v[y]=x;
}
sort(TT+1,TT+n+1,cmp);
con=0; i=1;
while (i<=n) {
S.push_back(bif);
while (TT[i].x==TT[i+1].x) {TT[i].x=con; i++;}
TT[i].x=con;
i++;
con++;
}
sort(TT+1,TT+n+1,cmp2);
for (i=1;i<=q;i++) {
fscanf(f,"%d%d%d",&ss,&x,&y);
if (ss==2) {
r=TT[x].x;
S[r].b[y]=true;
if (v[y]) {
if (!S[r].b[v[y]])
bv(v[y],r);
}
}
else {
if (S[TT[x].x].b[y]==true)
fprintf(g,"YES\n");
else
fprintf(g,"NO\n");
}
}
fclose(g);
return 0;
}