Cod sursa(job #1022415)

Utilizator nimeniaPaul Grigoras nimenia Data 5 noiembrie 2013 13:19:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <stack>

using namespace std;

const int MAX_N = 100000 + 2;
const int MAX_M = 200000 + 2;

vector<int> nodes[MAX_N];
vector<vector<int> > sccs;

int index[MAX_N], lowlink[MAX_N];

stack<int> s;
set<int> stack_nodes;

const int UNDEFINED = 0;

int current_index = 1;

inline void push(int node) {
  s.push(node);
  stack_nodes.insert(node);
}

inline void pop() {
  int node = s.top();
  s.pop();
  stack_nodes.erase(stack_nodes.find(node));
}


void connect(int node) {
  index[node] = current_index;
  lowlink[node] = current_index;
  current_index++;
  push(node);

  for (int i = 0; i < nodes[node].size(); i++) {
    int neighbour = nodes[node][i];
    if (index[neighbour] == UNDEFINED) {
      connect(neighbour);
      lowlink[node] = min(lowlink[node], lowlink[neighbour]);
    } else if (stack_nodes.find(neighbour) != stack_nodes.end()) {
      lowlink[node] = min(lowlink[node], index[neighbour]);
    }
  }

  vector<int> scc;
  if (lowlink[node] == index[node] && s.size() > 0) {
    int i;
    do {
      i = s.top();
      scc.push_back(i);
      pop();
    } while (node != i);
    sccs.push_back(scc);
  }

}

int main(int argc, char *argv[])
{
  
  int n, m, from, to;


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

  scanf("%d %d", &n, &m);

  for (int i = 0; i < m; i++) {
    scanf("%d %d", &from, &to);
    nodes[from].push_back(to);
  }

  for (int i = 1; i <= n; i++) {
    if (index[i] == UNDEFINED) 
      connect(i);
  }

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

  return 0;
}