Cod sursa(job #2928349)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 22 octombrie 2022 19:52:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
// Mihai Priboi

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000

int n, m;
vector<int> graph[MAXN + 1], revGraph[MAXN + 1];
vector<int> order;
vector<int> comp[MAXN + 1];

bool marked[MAXN + 1];

void dfs(int node, vector<int>* graph, vector<int>& v) {
  marked[node] = true;

  for(int neighbour : graph[node])
    if(!marked[neighbour])
      dfs(neighbour, graph, v);
      
  v.push_back(node);
}

int main() {
  FILE *fin, *fout;
  int i, x, y, node, compNo;
  fin = fopen("ctc.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &x, &y);
    graph[x].push_back(y);
    revGraph[y].push_back(x);
  }

  fclose(fin);

  for(i = 1; i <= n; i++)
    if(!marked[i])
      dfs(i, graph, order);

  memset(marked, 0, n + 1);

  compNo = 0;
  while(!order.empty()) {
    node = order.back();
    order.pop_back();
    if(!marked[node])
      dfs(node, revGraph, comp[compNo++]);
  }

  fout = fopen("ctc.out", "w");

  fprintf(fout, "%d\n", compNo);
  for(i = 0; i < compNo; i++) {
    for(int node : comp[i])
      fprintf(fout, "%d ", node);
    
    fprintf(fout, "\n");
  }

  fclose(fout);
  return 0;
}