Cod sursa(job #2121810)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 4 februarie 2018 12:56:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

const int NMAX = 100005;

ifstream input("ctc.in");
ofstream output("ctc.out");

vector<int> graph[NMAX], grapht[NMAX], components[NMAX];
int componentCount;
int n, m;
stack<int> st;
bitset<NMAX> used;

void readData() {
  input >> n >> m;
  int x, y;
  for (int i = 0; i < m; i++) {
    input >> x >> y;
    graph[x].push_back(y);
    grapht[y].push_back(x);
  }
}

void dfs(int node) {
  used[node] = 1;

  for (int y : graph[node]) {
    if (!used[y])
      dfs(y);
  }

  st.push(node);
}

void dfst(int node, int root) {
  used[node] = 1;
  components[root].push_back(node);

  for (int y : grapht[node]) {
    if (!used[y])
      dfst(y, root);
  }
}

void kosaraju() {
  for (int i = 1; i <= n; i++) {
    if (!used[i])
      dfs(i);
  }

  used.reset();

  while (!st.empty()) {
    int node = st.top();
    st.pop();
    if (!used[node]) {
      ++componentCount;
      dfst(node, node);
    }
  }
}

void printComponents() {
  output << componentCount << '\n';
  for (int i = 1; i <= n; i++) {
    if (components[i].empty())
      continue;
    for (int y : components[i])
      output << y << ' ';
    output << '\n';
  }
}

int main() {
  readData();
  kosaraju();
  printComponents();

  return 0;
}