Cod sursa(job #2149992)

Utilizator andrei.gramescuAndrei Gramescu andrei.gramescu Data 3 martie 2018 10:30:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
#define NMAX 100005
#define MMAX 200005

int n, m, nrcomp;
bool viz[NMAX];
vector<int> a[NMAX], ar[NMAX], sol[NMAX];
stack<int> st;

void DFS(int nod){
    viz[nod] = true;
    int i;
    for(i=0; i<(int) a[nod].size(); i++){
        if(!viz[ a[nod][i] ]){
            DFS( a[nod][i] );
        }
    }
    st.push(nod);
}

void DFSR(int nod){
    viz[nod] = true;
    sol[nrcomp].push_back(nod);
    int i;
    for(i=0; i<(int) ar[nod].size(); i++){
        if(!viz[ ar[nod][i] ]){
            DFSR( ar[nod][i] );
        }
    }
}

int main(){

    int i, j, x, y, z;
    FILE *fin, *fout;
    fin = fopen("ctc.in", "r");
    fout = fopen("ctc.out", "w");

    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d", &x, &y);
        a[x].push_back(y);
        ar[y].push_back(x);
    }

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

    memset(viz, false, sizeof(viz));

    while(!st.empty()){
        x = st.top();
        if(!viz[ x ]){
            nrcomp++;
            DFSR( x );
        }
        st.pop();
    }

    fprintf(fout, "%d\n", nrcomp);
    for(i=1; i<=nrcomp; i++){
        for(j=0; j<(int) sol[i].size(); j++){
            fprintf(fout, "%d ", sol[i][j]);
        }
        fprintf(fout, "\n");
    }

    //[email protected]

    return 0;
}