Cod sursa(job #2009019)

Utilizator Constantin.Dragancea Constantin Constantin. Data 8 august 2017 13:48:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

vector <int> V[100010], Inv[100010], Sol[100010];
int n,m,ord[100010],cnt,k;
bool u[100010];

void dfs(int q){
    u[q] = true;
    for (int i=0; i<V[q].size(); i++){
        if (!u[V[q][i]]) dfs(V[q][i]);
    }
    ord[++k] = q;
}

void dfsinv(int q){
    u[q] = false;
    for (int i=0; i<Inv[q].size(); i++){
        if (u[Inv[q][i]]) dfsinv(Inv[q][i]);
    }
    Sol[cnt].pb(q);
}

int main(){
    ifstream cin ("ctc.in");
    ofstream cout ("ctc.out");
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        int x, y;
        cin >> x >> y;
        V[x].pb(y);
        Inv[y].pb(x);
    }
    for (int i=1; i<=n; i++){
        if (!u[i]) dfs(i);
    }
    for (int i=n; i>=1; i--){
        if (u[ord[i]]) cnt++, dfsinv(ord[i]);
    }
    cout<<cnt<<"\n";
    for (int i=1; i<=cnt; i++){
        for (int j=0; j<Sol[i].size(); j++) cout<<Sol[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}