Cod sursa(job #2416485)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 27 aprilie 2019 16:46:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <bitset>

#define N 100005

using namespace std;

vector <int> g[N], sol[N];
stack <int> q;
int n,m,x,y,k;
int ix[N], llk[N], gix = 1;
bitset <N> viz;

void dfs(int nod){
    ix[nod] = llk[nod] = gix++;
    q.push(nod);
    viz[nod] = 1;

    for(int i : g[nod])
        if(!ix[i]){
            dfs(i);
            llk[nod] = min(llk[nod], llk[i]);
        }else if(viz[i])
            llk[nod] = min(llk[nod], ix[i]);

    if(llk[nod] == ix[nod]){
        int w;
        do{
            w = q.top();
            q.pop();
            sol[k].push_back(w);
            viz[w] = 0;
        }while(w!=nod);
        ++k;
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    scanf("%d%d", &n,&m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &x,&y);
        g[x].push_back(y);
    }

    for(int i = 1; i <= n; ++i)
        if(!ix[i])
            dfs(i);

    cout<<k<<"\n";
    for(int i = 0; i < k; ++i){
        for(int j : sol[i])
            cout<<j<<" ";
        cout<<"\n";
    }

    return 0;
}