Cod sursa(job #542367)

Utilizator S7012MYPetru Trimbitas S7012MY Data 26 februarie 2011 12:33:40
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.34 kb
#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";
            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;
}