Cod sursa(job #1714219)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 7 iunie 2016 19:17:10
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define N 100100
#define vec muc[k][i]

using namespace std;

vector<int> muc[N];
int grad[N],stk[N],viz[N],viz_stk[N];
int sp;
int low[N],prenum[N],ctc[3*N],ifin,nrctc;

int pop(){
    viz_stk[ stk[sp-1] ]=0;
    return stk[--sp];
}
void push(int x){
    viz_stk[ x ] = 1;
    stk[sp++]=x;
}

int cnt;
void dfs(int k){
    int i;

    push(k);
    viz[k]=1;
    prenum[k]=low[k]=++cnt;

    for(i=0;i<grad[k];i++){
        if( viz[vec]==0 ){
            dfs(vec);
            low[k]=min(low[k],low[vec] );

        }else{
            if(viz_stk[ vec ]==1){
                low[k]=min(low[k],prenum[vec]);
            }
        }
    }

    if(prenum[k]==low[k]){
        nrctc++;
        do{
            i=pop();
            ctc[ifin++]=i;
        }while(k!=i);
        ctc[ifin++]=-1;
    }

}


int main(){
    int i,n,m;
    int x,y;

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

    scanf("%d%d",&n,&m);

    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        muc[x].push_back(y);
        grad[x]++;
    }

    for(i=1;i<=n;i++){
        if(viz[i]==0){
            dfs(i);
        }
    }

    printf("%d\n",nrctc);
    for(i=0;i<ifin;i++){
        if(ctc[i]==-1){
            printf("\n");
            continue;
        }
        printf("%d ",ctc[i]);
    }

    return 0;
}