Cod sursa(job #542365)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 26 februarie 2011 12:31:14
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.02 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <iostream>
#define pb push_back

using namespace std;

int N, M, Q;
const int nmax = 100010;
int T[nmax], which[nmax];
vector<int> G[nmax];
vector<int> knows[nmax];
vector<int> about[nmax];
vector<int>::iterator it;
stack<int> S;

void read()
{

    freopen ("gossips.in","r",stdin);
    freopen ("gossips.out","w",stdout);
    scanf("%d %d %d",&N,&M,&Q);
    int a, b, i;
    for(i = 1; i <= M; i++)
    {
        scanf("%d %d",&a,&b);
        G[a].pb(b);
        T[b] = a;
    }
}

int mark;

void marque()
{
    int i, x;
    for(i = 1; i <= N; i++)
        if(!T[i])
        {
            S.push(i);
            which[i] = ++mark;
            while(!S.empty())
            {
                x = S.top();
                S.pop();
                for(it = G[x].begin(); it < G[x].end(); it++)
                {
                    which[*it] = mark;
                    S.push(*it);
                }
            }
        }
}

bool exist(int grup, int y)
{
    if(knows[grup].size() < about[y].size())
        for(it = knows[grup].begin(); it < knows[grup].end(); it++)
        {
            if(*it == y)
                return true;
        }
    else
    {
        for(it = about[y].begin(); it < about[y].end(); it++)
            if(*it == grup)
                return true;
    }
    return false;
}

int main()
{
    read();
    marque();
    int i, x, y, op, grup;
    for(i = 1; i <= Q; i++)
    {
        scanf("%d %d %d",&op,&x,&y);
        if(op == 1)
        {
            grup = which[x];
            if(exist(grup, y))
                printf("YES\n");
            else printf("NO\n");
        }
        else
        {
            grup = which[x];
            do
            {
                if(exist(grup,y))
                    break;
                knows[grup].pb(y);
                about[y].pb(grup);
                y = T[y];
            } while(y);
        }
    }

    return 0;
}