Cod sursa(job #734863)

Utilizator a08iAndrei Ionescu a08i Data 15 aprilie 2012 02:04:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;

typedef vector< vector<int> > Graph;

vector<int> explored, finish;
vector< vector<int> > sccs;
int cnt;
int how_many = 0;

void DFS1(Graph &graph, int i)
{
  explored[i] = 1;
  for(int j=0; j<graph[i].size(); j++)
  {
    if(explored[graph[i][j]] == 0)
    {
      DFS1(graph, graph[i][j]);
    }
  }
  finish[++cnt] = i;
}

void DFS2(Graph &graph, int i)
{
  explored[i] = 1;
  sccs[how_many].push_back(i);
  for(int j=0; j<graph[i].size(); j++)
  {
    if(explored[graph[i][j]] == 0)
    {
      DFS2(graph, graph[i][j]);
    }
  }
}


int main()
{

  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);

  int N, M, v1, v2;
  scanf("%d %d", &N, &M);

  Graph graph(N+1, vector<int>());
  Graph reverse(N+1, vector<int>());

  explored.resize(N+1);
  finish.resize(N+1);
  cnt = 0;

  for(int i=0; i<M; i++)
  {
    scanf("%d %d", &v1, &v2);
    graph[v1].push_back(v2);
    reverse[v2].push_back(v1);
  }

  // reverse
  for(int i=1; i<reverse.size(); i++)
  {
    if(explored[i] == 0)
    {
      DFS1(reverse, i);
    }
  }

  //  forward
  for(int i=0; i<explored.size(); i++)
  {
      explored[i] = 0;
  }

  for(int i=N; i>0; i--)
  {
    if(explored[finish[i]] == 0)
    {
      sccs.push_back(vector<int>());
      DFS2(graph, finish[i]);
      how_many++;
    }
  }

  printf("%d\n", how_many);

  for(int x=0; x<sccs.size(); x++)
  {
    for(int y=0; y<sccs[x].size(); y++)
    {
      printf("%d ", sccs[x][y]);
    }
    printf("\n");
  }

  return 0;
}