Cod sursa(job #1370971)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 3 martie 2015 18:23:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
#define pb push_back
#define nmax 100010

using namespace std;

bool used[nmax];
vector<int> a[nmax], at[nmax], sol[nmax];
int n, k, m, i, x, y, nrtcnx;
int ant[nmax];

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

    used[node]=true;

    for(it=a[node].begin(); it!=a[node].end(); ++it)
        if(!used[*it]) dfs(*it);

    ant[++k]=node;
}

void df(int node)
{
    vector<int>::iterator it;

    used[node]=false;
    sol[nrtcnx].pb(node);

    for(it=at[node].begin(); it!=at[node].end(); ++it)
        if(used[*it]) df(*it);
}
int main()
{
    freopen("ctc.in", "rt", stdin);
    freopen("ctc.out", "wt", stdout);

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

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

    for(i=1; i<=n; ++i)
        if(!used[i]) dfs(i);

    for(i=n; i>=1; --i)
    if(used[ant[i]])
    {
        ++nrtcnx;
        df(ant[i]);
    }

    printf("%d\n", nrtcnx);

    for(i=1; i<=nrtcnx; ++i)
    {
        for(vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); ++it)
        printf("%d ", *it);

        printf("\n");
    }

    return 0;
}