Cod sursa(job #1423701)

Utilizator Master011Dragos Martac Master011 Data 22 aprilie 2015 13:08:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include<cstdio>

const int nrMaxNoduri = 100000,
          nrMaxMuchii = 200000;
int st[nrMaxNoduri], vf, val[nrMaxMuchii], urm[nrMaxMuchii], lst[nrMaxNoduri], sol[2 * nrMaxNoduri],cnt,nrc;
int index[nrMaxNoduri], n, m, ind, low_level[nrMaxNoduri];
bool viz[nrMaxNoduri], in_stack[nrMaxNoduri];

int minim (int a, int b){
    return a<b?a:b;
}

void dfs (int node){
    int pozc = vf;

    viz[node] = 1;
    low_level[node] = index[node] = ++ind;
    st[vf++] = node;
    in_stack[node] = 1;

    int pozv = lst[node], vec;

    while(pozv != -1){
        vec = val[pozv];
        if(!viz[vec]){
            dfs(vec);
            low_level[node] = minim(low_level[node], low_level[vec]);
        }else if(in_stack[vec]){
            low_level[node] = minim(low_level[node], low_level[vec]);
        }

        pozv = urm[pozv];
    }

    if(index[node] == low_level[node]){
        //Putem considera nodul ca fiind radacina componentei tare conexe
        ++nrc;
        sol[cnt++] = vf  - pozc;
        int nd;
        do{
            nd = st[--vf];
            in_stack[nd] = 0;
            sol[cnt++] = nd;
        }while(nd != node);
    }
}


int main (){
    FILE *in = fopen("ctc.in","r");
    FILE *out = fopen("ctc.out","w");

    fscanf(in,"%d%d",&n,&m);

    for(int i = 0 ; i < n ; i++) lst[i] = -1;

    int x, y;
    for(int i = 0 ; i < m ; i++){
        fscanf(in,"%d%d",&x,&y);
        y--;x--;
        val[i] = y;
        urm[i] = lst[x];
        lst[x] = i;
    }

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

    fprintf(out,"%d\n",nrc);

    for(int i = 0 , j = 0 ; i < cnt ; i++){
        if(j == 0){
            j = sol[i];
        }else{
            j--;
            fprintf(out,"%d ",sol[i] + 1);
        }

        if(j == 0){
            fprintf(out,"\n");
        }
    }

    return 0;
}