Cod sursa(job #3216008)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 15 martie 2024 15:53:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <vector>

#define MAXN 100010
using namespace std;

struct node{
  int lvl, currLvl, t;
  vector <int> neighbours;
};

node graph[MAXN];
vector <int> ans[MAXN];
int ansSize;
int t;
int dfsId;
vector <int> aux;

void dfs(int pos) {
  graph[pos].currLvl = graph[pos].lvl = t;
  graph[pos].t = dfsId;
  aux.push_back(pos);
  t++;

  for ( int v : graph[pos].neighbours ) {
    if ( graph[v].t == 0 || graph[v].t == dfsId ) {
      if ( graph[v].t == 0 ) {
        dfs(v);
      }
      graph[pos].lvl = min(graph[pos].lvl, graph[v].lvl);
    }
  }

  if ( graph[pos].currLvl == graph[pos].lvl ) {
    while ( aux.back() != pos ) {
      ans[ansSize].push_back(aux.back());
      aux.pop_back();
    }
    ans[ansSize].push_back(pos);
    ansSize++;
    aux.pop_back();
  }
}

void addEdge(int a, int b) {
  graph[a].neighbours.push_back(b);
}

int main() {
  FILE *fin, *fout;
  fin = fopen("ctc.in", "r");
  fout = fopen("ctc.out", "w");

  int n, m, i, a, b;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d", &a, &b);

    addEdge(a, b);
  }

  dfsId = 1;
  ansSize = 0;

  for ( i = 1; i <= n; i++ ) {
    if ( !graph[i].t ) {
      dfs(i);
      dfsId++;
    }
  }

  fprintf(fout, "%d\n", ansSize);
  for ( i = 0; i < ansSize; i++ ) {
    for ( int v : ans[i] ) {
      fprintf(fout, "%d ", v);
    }
    fprintf(fout, "\n");
  }

  fclose(fin);
  fclose(fout);

  return 0;
}