Cod sursa(job #1540781)

Utilizator danny794Dan Danaila danny794 Data 3 decembrie 2015 11:11:58
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <cstdio>
#include <stack>
#include <vector>

#define NMAX 100005
#define INF  (1 << 30)

using namespace std;

struct node {
  bool onStack;
  int component;
  int minim;
  vector<int> edges;

  node() {
    onStack = false;
    component = INF;
  }
};

int n, m, count;
struct node* nodes[NMAX];
vector<stack<int> > solution;
stack<int> s;

void readInput() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    nodes[i] = new struct node();
  }
  int a, b;
  while (m > 0) {
    scanf("%d %d", &a, &b);
    nodes[a]->edges.push_back(b);
    m--;
  }
}

void push(int index) {
  struct node* vNode = nodes[index];
  vNode->onStack = true;
  vNode->component = vNode->minim = ++count;
  s.push(index);
//  printf("Marked %d with %d\n", index, vNode->component);
}

void pop(int index) {
  struct node* vNode = nodes[index];
  solution.push_back(stack<int>());
  while (!s.empty()) {
    int top = s.top();
    if (vNode->minim <= nodes[top]->minim) {
//      printf("Pop %d with %d\n", top, vNode->minim);
      nodes[top]->onStack = false;
      s.pop();
      solution.back().push(top);
    } else {
      break;
    }
  }
}

void visit(int index) {
  struct node* vNode = nodes[index];
  push(index);
  for (int i = 0; i < vNode->edges.size(); i++) {
    int childIndex = vNode->edges[i];
    struct node* child = nodes[childIndex];
    if (child->component == INF) {
      visit(childIndex);
      vNode->minim = min(vNode->minim, child->minim);
    } else if (child->onStack) {
      vNode->minim = min(vNode->minim, child->minim);
    }
  }
//  printf("Node %d finished with %d\n", index, vNode->minim);
  if (vNode->minim == vNode->component) {
    pop(index);
  }
}

int main() {
  readInput();
  for (int i = 1; i <= n; i++) {
    if (nodes[i]->component == INF) {
      visit(i);
    }
  }
  printf("%d\n", solution.size());
  for (int i = 0; i < solution.size(); i++) {
    while (!solution[i].empty()) {
      printf("%d ", solution[i].top());
      solution[i].pop();
    }
    printf("\n");
  }
  return 0;
}