Cod sursa(job #1471960)

Utilizator S7012MYPetru Trimbitas S7012MY Data 15 august 2015 18:34:38
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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;
vector<int> gr[DN];
vector<vector<int> > ctc;

void dfs(int s,int hc) {
    h[s]=low[s]=hc;
    st[++sz]=s;
    ist[s]=1;
    //cout<<"Incep dfs: "<<s<<'\n';
    for(it i=gr[s].begin(); i!=gr[s].end(); ++i) {
        if(!h[*i]) dfs(*i,hc+1);
        if(ist[*i]) low[s]=min(low[s],low[*i]);
    }
    //cout<<s<<' '<<h[s]<<' '<<low[s]<<'\n';
    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("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    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,1);
    cout<<ctc.size()<<'\n';
    for(int i=0; i<ctc.size(); ++i) {
        for(int j=0; j<ctc[i].size(); ++j) cout<<ctc[i][j]<<' ';
        cout<<'\n';
    }
}