Cod sursa(job #542440)

Utilizator S7012MYPetru Trimbitas S7012MY Data 26 februarie 2011 13:27:30
Problema Gossips Scor 30
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.36 kb
#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;
}