Cod sursa(job #542393)

Utilizator david_raucaRauca Ioan David david_rauca Data 26 februarie 2011 12:54:43
Problema Gossips Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.8 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 y );

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

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

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