Cod sursa(job #542352)

Utilizator david_raucaRauca Ioan David david_rauca Data 26 februarie 2011 12:15:17
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.46 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("gossips.in");
ofstream fout("gossips.out");

vector<vector<int> > G;

bool s[100001];

int ok;

int n, m, q;
int y, t;

void Read();
void DF( int x );

int main()
{
    Read();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n >> m >> q;
     int x;
     G.resize(n+1);
     for( int i = 1; i <= m; ++i )
     {
          fin >> x >> y;
          G[y].push_back(x);
          //G[y].push_back(x);
     }
     
     for( int i = 1; i <= q; ++i )
     {
          fin >> t >> x >> y;
          if( t == 2 )
              G[x].push_back(y);
          else
          {
              ok = 0;
              DF( x );
              if( ok == 0 )
                  fout << "NO" <<'\n';
              
              for( int j = 1; j <= n; ++j )
              {
                   s[j]= false;
                   //fout << s[j] << ' ';
                   }
              //fout << '\n';
              
          }
     }
}

void DF( int x )
{
     if( ok == 1 )
         return;
     if( x == y )
     {
         fout << "YES" << '\n';
         ok = 1;
         return;
     }
     s[x] = true;
     
     for( int i = 0; i < G[x].size(); ++i )
          if( !s[ G[x][i] ] && ok == 0 )
          {
              DF( G[x][i] );
              
              if( ok == 1 )
                  return;
          }
}