Cod sursa(job #2401443)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 aprilie 2019 18:36:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 100000
#define MAXM 200000
#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[MAXM], nxt[MAXM], dr;
int dep[MAXN], dth = 1;
char pus[MAXN];
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){
  if(x == 485){
    x++;
    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(!pus[nd[p]]){
      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());
      pus[s.back()] = 1;
      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(!pus[i]){
      group(i);
    }
  }
  printf("%d\n", comp.size());
  for(auto &it : comp){
    for(auto &it2 : it){
      printf("%d ", it2 + 1);
    }
    fputc('\n', stdout);
  }
  return 0;
}