Cod sursa(job #1095416)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 30 ianuarie 2014 21:49:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 100005

vector <int> graph[Nmax], graphT[Nmax];
int visited[Nmax], f[Nmax];
int n, m, k, comp;

void read()
{
    int x, y;
    freopen("ctc.in", "r", stdin);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i){
        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }
    fclose(stdin);
}

void dfs1(int node)
{
    vector <int>::iterator it;
    visited[node] = 1;
    for (it = graph[node].begin(); it != graph[node].end(); ++it)
        if (!visited[*it])
            dfs1(*it);
    f[++k] = node;
}

void dfs2(int node)
{
    vector <int>::iterator it;
    visited[node] = 0;
    for (it = graphT[node].begin(); it != graphT[node].end(); ++it)
        if (visited[*it])
            dfs2(*it);
}

void dfs3(int node)
{
    printf("%d ", node);
    vector <int>::iterator it;
    visited[node] = 1;
    for (it = graphT[node].begin(); it != graphT[node].end(); ++it)
        if (!visited[*it])
            dfs3(*it);
}

void ctc()
{
    freopen("ctc.out", "w", stdout);

    for (int i = 1; i <= n; ++i)
        if(!visited[i])
            dfs1(i);
    for (int i = n; i > 0; --i)
        if(visited[ f[i] ]){
            ++comp;
            dfs2( f[i] );
        }
    printf("%d\n", comp);
    for (int i = n; i > 0; --i)
        if(!visited[ f[i] ]){
            dfs3( f[i] );
            printf("\n");
        }
    fclose(stdout);
}

int main()
{
    read();
    ctc();

    return 0;
}