Cod sursa(job #780750)

Utilizator visanrVisan Radu visanr Data 21 august 2012 11:09:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;


#define nmax 100010

int index[nmax], lowLink[nmax], N, M, X, Y, number = 1;
bool InStack[nmax];
stack<int> S;
vector<int> G[nmax];
vector<vector<int> > ctc;


void Tarjan(int startNode);


int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int i, j;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i", &X, &Y);
          G[Y].push_back(X);
    }
    for(i = 1; i <= N; i++)
          if(index[i] == 0)
                      Tarjan(i);
    printf("%i\n", ctc.size());
    for(i = 0; i < ctc.size(); i++)
    {
          for(j = 0; j < ctc[i].size(); j++) printf("%i ", ctc[i][j]);
          printf("\n");
    }
    return 0;
}


void Tarjan(int startNode)
{
     index[startNode] = lowLink[startNode] = number ++;
     S.push(startNode);
     InStack[startNode] = true;
     for(vector<int> :: iterator it = G[startNode].begin(); it != G[startNode].end(); ++it)
     {
                     if(index[*it] == 0)
                     {
                                   Tarjan(*it);
                                   lowLink[startNode] = min(lowLink[startNode], lowLink[*it]);
                     }else
                     {
                          if(InStack[*it])
                          {
                                          lowLink[startNode] = min(lowLink[startNode], index[*it]);
                          }
                     }
     }
     if(lowLink[startNode] == index[startNode])
     {
                           vector<int> New;
                           int node = 0;
                           while(node != startNode)
                           {
                                      node = S.top();
                                      S.pop();
                                      New.push_back(node);
                                      InStack[node] = false;
                           }
                           ctc.push_back(New);
     }
}