Cod sursa(job #2401429)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 aprilie 2019 18:26:11
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 10000
#define MAXM 20000
#define vi vector<int>
#define vvi vector<vi>
#define pb(x) push_back(x)
#define pp() pop_back()
using namespace std;
int ut[MAXN], nd[2 * MAXM], nxt[2 * MAXM], dr;
int dep[MAXN], dth = 1, mndth;
vvi comp;
int dc;
vi s;

void add(int x, int y){
  nd[dr] = y;
  nxt[dr] = ut[x];
  ut[x] = dr;
  dr++;
}

void group(int x){
  s.pb(x);
  int p = ut[x], md = dth;
  dep[x] = dth++;
  while(p != -1){
    if(dep[nd[p]] == 0){
      group(nd[p]);
      if(dep[nd[p]] < dep[x])
        dep[x] = dep[nd[p]];
    }
    else  if(dep[nd[p]] >= mndth){
      if(dep[nd[p]] < dep[x])
        dep[x] = dep[nd[p]];
    }
    p = nxt[p];
  }
  if(dep[x] == md){
    vi aux;
    do{
      aux.pb(s.back());
      s.pp();
    }while(aux.back() != x);
    comp.pb(aux);
    dc++;
  }
}

int main(){
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  int n, m, i, x, y;
  scanf("%d%d", &n, &m);
  memset(ut, -1, sizeof ut);
  for(i = 0; i < m; i++){
    scanf("%d%d", &x, &y);
    x--;
    y--;
    add(x, y);
  }
  for(i = 0; i < n; i++){
    if(dep[i] == 0){
      mndth = dth;
      group(i);
    }
  }
  printf("%d\n", comp.size());
  for(auto &it : comp){
    for(auto &it2 : it){
      printf("%d ", it2 + 1);
    }
    fputc('\n', stdout);
  }
  return 0;
}