Cod sursa(job #1006281)

Utilizator MKLOLDragos Ristache MKLOL Data 6 octombrie 2013 19:57:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

#define pb push_back

using namespace std;

vector<int> g[102020],stack,viz,low,iss;
vector<int> aux;
vector<vector <int> > comp;
int k,index=1;
int N,M,x,y;

void printv(vector<int> v){

    for(int i=0;i<v.size();++i){
        printf("%d ",v[i]);
    }
    printf("\n");
}

void df(int x){

    viz[x] = index;
    low[x] = index;
    stack[++k] = x;
    iss[x] = 1;
    ++index;
    for(int i=0;i<g[x].size();++i){
        if(viz[g[x][i]] == 0){
            df(g[x][i]);
            low[x] = min(low[x],low[g[x][i]]);
        }
        else{
            if(iss[g[x][i]]){
                low[x] = min(low[x],low[g[x][i]]);
            }
        }
    }
    if(low[x] == viz[x]){

        aux.clear();

        do{
            aux.pb(stack[k]);
            iss[stack[k]] = 0;
            --k;
        }while(stack[k+1] != x);

        comp.pb(aux);
    }
}

void init(){
    stack.resize(N+10);
    viz.resize(N+10);
    iss.resize(N+10);
    low.resize(N+10);
}

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

scanf("%d%d",&N,&M);

    init();


    for(int i=1;i<=M;++i){
        scanf("%d%d",&x,&y);
        g[x].pb(y);
    }
    for(int i=1;i<=N;++i){
        if(viz[i]==0){
            df(i);
        }
    }
    printf("%d\n",comp.size());

    for(int i=0;i<comp.size();++i){
        printv(comp[i]);
    }
    return 0;
}