Mai intai trebuie sa te autentifici.

Cod sursa(job #782683)

Utilizator visanrVisan Radu visanr Data 28 august 2012 18:39:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;


#define nmax 100010
int ind[nmax], lowLink[nmax], number = 1, N, M, X, Y;
bool InStack[nmax];
stack<int> S;
vector<int> G[nmax];
vector<vector<int> > CTC;

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

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(!ind[i])
                     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;
}