Cod sursa(job #1471973)

Utilizator S7012MYPetru Trimbitas S7012MY Data 15 august 2015 19:26:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <vector>
#include <cstdio>
#define DN 100005
using namespace std;

typedef vector<int>::iterator it;

int n,m,low[DN],h[DN],st[DN],ist[DN],sz,nrn;
vector<int> gr[DN];
vector<vector<int> > ctc;

void dfs(int s) {
    h[s]=low[s]=++nrn;
    st[++sz]=s;
    ist[s]=1;
    for(it i=gr[s].begin(); i!=gr[s].end(); ++i) {
        if(!h[*i]) dfs(*i);
        if(ist[*i]) low[s]=min(low[s],low[*i]);
    }
    if(h[s]==low[s]) {
        vector<int> cc;
        while(st[sz]!=s) {
            ist[st[sz]]=0;
            cc.push_back(st[sz]);
            --sz;
        }
        ist[s]=0;
        cc.push_back(s);
        --sz;
        ctc.push_back(cc);
    }
}

int main() {
    //freopen("input.txt","r",stdin);
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    cin.sync_with_stdio(false);
    for(cin>>n>>m;m--;) {
        int a,b; cin>>a>>b;
        gr[a].push_back(b);
    }
    for(int i=1; i<=n; ++i) if(!h[i])
        dfs(i);
    cout<<ctc.size()<<'\n';
    for(int i=0; i<ctc.size(); ++i) {
        for(it j=ctc[i].begin(); j!=ctc[i].end(); ++j) cout<<*j<<' ';
        cout<<'\n';
    }
}