Cod sursa(job #2391275)

Utilizator Constantin.Dragancea Constantin Constantin. Data 28 martie 2019 18:57:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

#define N 100005
int n, m, low[N], ord[N], inv[N], k, c, st[N], vf;
vector <int> v[N], ctc[N];
bool inS[N];

void dfs(int q){
    ord[q] = low[q] = ++k;
    st[++vf] = q; inS[q] = 1;
    for (auto it: v[q]){
        if (!ord[it]) dfs(it), low[q] = min(low[it], low[q]);
        else if (inS[it]) low[q] = min(low[q], ord[it]);
    }
    if (low[q] == ord[q]){
        c++;
        while (st[vf] != q){
            ctc[c].push_back(st[vf]);
            inS[st[vf--]] = 0;
        }
        ctc[c].push_back(st[vf]);
        inS[st[vf--]] = 0;
    }
}

int main(){
    ifstream cin ("ctc.in");
    ofstream cout ("ctc.out");
    cin >> n >> m;
    for (int i=1, x, y; i<=m; i++){
        cin >> x >> y;
        v[x].push_back(y);
    }
    for (int i=1; i<=n; i++)
        if (!ord[i]) dfs(i);
    cout << c << '\n';
    for (int i=1; i<=c; i++, cout << '\n'){
        sort(ctc[i].begin(), ctc[i].end());
        for (auto it: ctc[i]) cout << it << ' ';
    }
    return 0;
}