Cod sursa(job #1279726)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 30 noiembrie 2014 19:51:01
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>
#define nmax 100001
#define pb push_back

using namespace std;

vector<int> g[nmax], gt[nmax];

bool viz[nmax];
int n, m, i,  k, nr, ordine[nmax], conex[nmax], x, y;

void dfs(int nod)
{
    vector <int>::iterator it;

    viz[nod]=1;

    for(it=g[nod].begin(); it!=g[nod].end(); ++it)
        if(!viz[*it]) dfs(*it);
    ordine[++k]=nod;
}

void dfst(int nod)
{
    conex[nod]=nr;
    viz[nod]=0;

    vector<int>::iterator it;

    for(it=gt[nod].begin(); it!=gt[nod].end(); ++it)
        if(viz[*it]) dfst(*it);
}

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

    scanf("%d%d", &n, &m);

    for(i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        g[x].pb(y);
        gt[y].pb(x);
    }

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

    for(i=n; i>=1; --i)
    if(viz[ordine[i]])
    {
        ++nr;
        dfst(ordine[i]);
    }
    printf("%d\n", nr);
    for(i=1; i<=nr; ++i)
    {
        for(int j=1; j<=n; ++j) if(conex[j]==i) printf("%d ", j);
        printf("\n");
    }
}