Cod sursa(job #2981402)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 17 februarie 2023 21:05:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <vector>
#include <memory>
#include <stack>

using namespace std;

class Solver{
private:
  stack<int> kosarajuStack;
  vector<bool> used;

  void DFS(const vector<vector<int>>& Graph, int k) {
    used[k] = true;
    for (auto v: Graph[k])
      if (!used[v])
	DFS(Graph, v);
    kosarajuStack.emplace(k);
  }

  void DFST(const vector<vector<int>>& GraphT, int k, vector<int>& ctc) {
    used[k] = true;
    for (auto v: GraphT[k])
      if (!used[v])
	DFST(GraphT, v, ctc);
    ctc.emplace_back(k);
  }
  
  vector<vector<int>> kosaraju(const vector<vector<int>>& Graph) {
    vector<vector<int>> GraphT((int)Graph.size());
    for (int curNode = 0; curNode < (int)Graph.size(); ++curNode)
      for (auto v: Graph[curNode])
	GraphT[v].emplace_back(curNode);

    used.resize((int)Graph.size());
    for (int i = 0; i < (int)Graph.size(); ++i)
      if (!used[i])
	DFS(Graph, i);

    fill(used.begin(), used.end(), false);
    vector<vector<int>> ctcs;
    int k = -1;
    while (!kosarajuStack.empty()) {
      k = kosarajuStack.top();
      kosarajuStack.pop();
      if (used[k])
	continue;
      vector<int> ctc;
      DFST(GraphT, k, ctc);
      ctcs.emplace_back(ctc);
    }
    return ctcs;
  }
  
public:
  Solver() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void execute() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<vector<int>> Graph(N);
    int from, to;
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &from, &to);
      --from; --to;
      Graph[from].emplace_back(to);
    }
    vector<vector<int>> ctcs = kosaraju(Graph);
    printf("%d\n", (int)ctcs.size());
    for (auto ctc: ctcs) {
      for (auto v: ctc)
	printf("%d ", v + 1);
      printf("\n");
    }	
  }
};

int main() {
  unique_ptr<Solver> s = make_unique<Solver>();
  s->execute();
  return 0;
}