Cod sursa(job #2926604)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 18 octombrie 2022 10:21:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <vector>

#define MAXN 100000
using namespace std;

struct node{
  vector <int> edges;
  int smallestLvl;
  bool isInStack;
  bool visited;
  int posInV;
};

node graph[MAXN + 1];
int v[MAXN];
int vSize;
vector <int> ans[MAXN];
int ansSize;
int lvl;

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

void dfs(int pos) {
  int i, lvlPos;

  graph[pos].smallestLvl = lvl;
  lvlPos = lvl;
  lvl++;
  v[vSize] = pos;
  vSize++;
  graph[pos].isInStack = true;
  graph[pos].visited = true;
  for ( int i : graph[pos].edges ) {
    if ( graph[i].smallestLvl == -1 ) {
      dfs(i);
      graph[pos].smallestLvl = min(graph[pos].smallestLvl, graph[i].smallestLvl);
    }
    if ( graph[i].isInStack ) {
      graph[pos].smallestLvl = min(graph[pos].smallestLvl, graph[i].smallestLvl);
    }
  }

  if ( graph[pos].smallestLvl == lvlPos ) {
    do {
      vSize--;
      ans[ansSize].push_back(v[vSize]);
      graph[v[vSize]].isInStack = false;
      graph[v[vSize]].smallestLvl = lvl;
    } while ( v[vSize] != pos );
    ansSize++;
  }
}

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

  int n, m, i, a, b, i2;

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

  for ( i = 1; i <= n; i++ ) {
    graph[i].smallestLvl = -1;
  }

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

    addEdge(a, b);
  }

  vSize = ansSize = 0;
  for ( i = 1; i <= n; i++ ) {
    if ( !graph[i].visited ) {
      lvl = 0;
      dfs(i);
    }
  }

  fprintf(fout, "%d\n", ansSize);
  for ( i = 0; i < ansSize; i++ ) {
    for ( i2 = 0; i2 < ans[i].size(); i2++ ) {
      fprintf(fout, "%d ", ans[i][i2]);
    }
    fprintf(fout, "\n");
  }

  return 0;
}