Cod sursa(job #922937)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 22 martie 2013 18:41:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>
#include <vector>
#include <list>
#include <time.h>
using namespace std;

#define Nmax 100005

vector< list <int> > graf, grafT;
int visited[Nmax], finishOrder[Nmax];
int n, m, c, comp;

void read(){
    int x, y;
    scanf("%i %i", &n, &m);
    graf.resize(n+1);
    grafT.resize(n+1);

    for(int i = 1; i <= m; ++i){
        scanf("%i %i", &x, &y);
        graf[x].push_back(y);
        grafT[y].push_back(x);
    }

    fclose(stdin);
}

void dfs(int v){
    list <int>::iterator it;
    visited[v] = 1;
    for(it = graf[v].begin(); it != graf[v].end(); ++it)
        if(!visited[*it])
            dfs(*it);
    finishOrder[++c] = v;
}

void dfsT(int v){
    list <int>::iterator it;
    visited[v] = 0;
    for(it = grafT[v].begin(); it != grafT[v].end(); ++it)
        if(visited[*it])
            dfsT(*it);
}

void dfsTS(int v){
    printf("%i ", v);
    list <int>::iterator it;
    visited[v] = 1;
    for(it = grafT[v].begin(); it != grafT[v].end(); ++it)
        if(!visited[*it])
            dfsTS(*it);
}

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

    clock_t tStart = clock();

    read();
    for(int i = 1; i <= n ; ++i)
        if(!visited[i])
            dfs(i);

    for(int i = n; i >= 1; --i)
        if(visited[ finishOrder[i] ]){
            ++comp;
            dfsT( finishOrder[i] );
        }

    printf("%i\n", comp);

    for(int i = n; i >= 1; --i)
        if(!visited[ finishOrder[i] ]){
            dfsTS( finishOrder[i] );
            printf("\n");
        }
    printf("Time taken: %.2fms\n", (double)(clock() - tStart)/CLOCKS_PER_SEC*1000);
}