Cod sursa(job #3200244)

Utilizator cata00Catalin Francu cata00 Data 3 februarie 2024 21:58:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
// Strongly connected components - Tarjan's algorithm.
#include <algorithm>
#include <stack>
#include <stdio.h>
#include <vector>

const int MAX_NODES = 100'000;

struct node {
  std::vector<int> adj, adjt;
  int time_in;
  int low;
  bool on_stack;
};

node n[MAX_NODES + 1];
std::stack<int> st;  // DFS stack
std::vector<std::vector<int>> comps;
int num_nodes, time;

void read_graph() {
  FILE* f = fopen("ctc.in", "r");
  int num_edges, u, v;
  fscanf(f, "%d %d", &num_nodes, &num_edges);
  for (int i = 1; i <= num_edges; i++) {
    fscanf(f, "%d %d", &u, &v);
    n[u].adj.push_back(v);
  }
  fclose(f);
}

void pop_scc(int last) {
  std::vector<int> c;
  int v;
  do {
    v = st.top();
    st.pop();
    c.push_back(v);
    n[v].on_stack = false;
  } while (v != last);
  comps.push_back(c);
}

void dfs(int u) {
  n[u].time_in = n[u].low = ++time;
  n[u].on_stack = true;
  st.push(u);

  for (auto v: n[u].adj) {
    if (!n[v].time_in) {
      // Traverse the white descendant and make a note of how high it can
      // climb.
      dfs(v);
      n[u].low = std::min(n[u].low, n[v].low);
    } else if (n[v].on_stack) {
      // We can climb to v's level.
      n[u].low = std::min(n[u].low, n[v].time_in);
    }
  }

  // If no vertex from u's subtree can climb higher than u, then the stack
  // from u to the top is a SCC.
  if (n[u].low == n[u].time_in) {
    pop_scc(u);
  }
}

void dfs_driver() {
  for (int u = 1; u <= num_nodes; u++) {
    if (!n[u].time_in) {
      dfs(u);
    }
  }
}

void write_components() {
  FILE* f = fopen("ctc.out", "w");
  fprintf(f, "%lu\n", comps.size());
  for (auto vec: comps)  {
    for (auto u: vec) {
      fprintf(f, "%d ", u);
    }
    fprintf(f, "\n");
  }
  fclose(f);
}

int main() {
  read_graph();
  dfs_driver();
  write_components();

  return 0;
}