Cod sursa(job #235536)

Utilizator filipbFilip Cristian Buruiana filipb Data 24 decembrie 2008 12:43:11
Problema Componente tare conexe Scor Ascuns
Compilator cpp Status done
Runda Marime 1.26 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMax 100005
#define pb push_back 

int N, M, ctc[NMax], times[NMax], t, uz[NMax], cnt;
vector<int> G[NMax], GT[NMax], Sol[NMax];

void df(int nod)
{
    int i, sz, x;
    
    uz[nod] = 1;
    for (i = 0, sz = G[nod].size(); i < sz; ++i)
        if (!uz[x = G[nod][i]])
            df(x);
    times[++t] = nod;
}

void df2(int nod)
{
    int i, sz, x;
    
    ctc[nod] = cnt; Sol[cnt].pb(nod);
    for (i = 0, sz = GT[nod].size(); i < sz; ++i)
        if (!ctc[x = GT[nod][i]])
            df2(x);
}

int main()
{
    int i, u, v, sz;
    
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    
    scanf("%d %d", &N, &M);
    for (; M; --M)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        GT[v].push_back(u);
    }

    for (i = 1; i <= N; ++i)
        if (!uz[i])
            df(i);
    for (i = N; i; --i)
        if (!ctc[times[i]])
        {
            ++cnt;
            df2(times[i]);
        }
    
    printf("%d\n", cnt);
    for (i = 1; i <= cnt; ++i)
    {
        for (sz = Sol[i].size(), u = 0; u < sz; ++u)
            printf("%d ", Sol[i][u]);
        printf("\n");
    }

    return 0;
}