Cod sursa(job #300193)

Utilizator alecmanAchim Ioan Alexandru alecman Data 7 aprilie 2009 11:56:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

#define INPUT "ctc.in"
#define OUTPUT "ctc.out"

const long NMAX = 100001;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, M, cont, final;
long mindf[ NMAX ], nrdf[ NMAX ];
vector<long> List[ NMAX ], Final[ NMAX ];
stack<long> stk;
bool viz[ NMAX ], added[ NMAX ];

inline long MIN(long X, long Y)
{
  if(X<Y) return X;
  return Y;
}

void readData()
{
  long Node1, Node2;
  
  fscanf(fin, "%ld %ld", &N, &M);
  
  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld", &Node1, &Node2);
    
    List[ Node1 ].push_back(Node2);
  }
}

void tarjan(long Node)
{
  nrdf[ Node ] = cont;
  mindf[ Node ] = cont;
  ++cont;
  
  stk.push(Node);
  added[ Node ] = 1;
  
  vector<long>::iterator it;
  
  for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
  {
    if(nrdf[ *it ] == -1 || added[ *it ])
    {
      if(nrdf[ *it ] == -1) tarjan(*it);
    
      mindf[ Node ] = MIN( mindf[ Node ], mindf[ *it ]);
    }
  }
  
  long nnod;
  
  if(mindf[ Node ] == nrdf[ Node ])
  {
    ++final;
    do{
      nnod = stk.top();
      stk.pop();
      Final[ final ].push_back(nnod);
    }while(nnod != Node);
  }
}

int main()
{
  readData();
  
  cont = 0;
  final = 0;
  vector<long>::iterator it;
  
  for(long i = 1; i <= N; ++i)
    nrdf[ i ] = -1, mindf[ i ] = -1;
  
  for(long i = 1; i <= N; ++i)
    if(nrdf[ i ] == -1)
      tarjan(i);
      
  fprintf(fout, "%ld\n", final);
      
  for(long i = 1; i <= final; ++i)
  {
    for(it = Final[ i ].begin(); it != Final[ i ].end(); ++it)
      fprintf(fout, "%ld ", *it);
    fprintf(fout, "\n");
  }
  
  fclose(fin);
  fclose(fout);
  
  return 0;
}