Cod sursa(job #1751108)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 31 august 2016 18:49:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

int          ant, clev;
vector<int>  stk;
vector<int>    g[NMAX],
             ctc[NMAX];
int          lvl[NMAX],
             low[NMAX];
bool         gws[NMAX], ///gewesen, ja...
             isk[NMAX];

void dfs(int nod) {
    stk.push_back(nod);
    lvl[nod] = ++clev;
    low[nod] =   clev;
    isk[nod] =   true;
    gws[nod] =   true;

    for(auto i:g[nod]) {
        if(!gws[i])
            dfs(i);
        if(isk[i])
            low[nod] = min(low[nod], low[i]);
    }

    if(lvl[nod]==low[nod]) {
        int c;
        do {
            c = stk.back();
            ctc[ant].push_back(c);
            isk[c] = false;
            stk.pop_back();
        } while(c!=nod);
        ++ant;
    }
}

int main(void) {
    freopen("ctc.in",  "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m, x, y;

    scanf("%d%d",&n,&m);
    while(m--) {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }

    for(int i=1; i<=n; ++i) if(!gws[i]) {
        clev = 0;
        dfs(i);
    }

    printf("%d\n",ant);
    for(int i=0; i<ant; ++i) {
        for(int j:ctc[i])
            printf("%d ", j);
        printf("\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}