Cod sursa(job #3150680)

Utilizator victorzarzuZarzu Victor victorzarzu Data 17 septembrie 2023 22:44:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <algorithm>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<int> graph[100001], grapht[100001];
bool viz[100001];
vector<int> topo;

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

void dfs(const int& node) {
  viz[node] = true;
  for(const auto& ngh : graph[node]) {
    if(!viz[ngh]) {
      dfs(ngh);
    }
  }

  topo.push_back(node);
}

void dfst(const int& node, vector<int>& comp) {
  viz[node] = false;
  comp.push_back(node);
  for(const auto& ngh : grapht[node]) {
    if(viz[ngh]) {
      dfst(ngh, comp);
    }
  }
}

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

  vector<vector<int>> result;
  for(auto it = topo.rbegin();it != topo.rend();++it) {
    if(viz[*it]) {
      vector<int> comp;
      dfst(*it, comp);
      result.push_back(comp);
    }
  }

  g<<result.size()<<'\n';
  for(const auto& comp : result) {
    for(const auto& node : comp) {
      g<<node<<" ";
    }
    g<<'\n';
  }
}

int main() {
  read();
  solve();
  return 0;
}