Cod sursa(job #1707070)

Utilizator andru47Stefanescu Andru andru47 Data 24 mai 2016 09:31:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int NMAX = 100000 + 5;
vector <int> g[NMAX],gt[NMAX];
int n,m,N,ret,st[NMAX],x,y;
bool sel[NMAX];
inline void df1(int x)
{
    sel[x] = true;
    for (int i = 0 ; i<g[x].size(); ++i)
        if (sel[g[x][i]]==false)
        {
            df1(g[x][i]);
        }
    st[++N] = x;
}
inline void df2(int x, bool ok)
{
    sel[x] = true;
    if (ok==true)printf("%d ", x);
    for (int i = 0; i<gt[x].size(); ++i)
        if (sel[gt[x][i]]==false)
            df2(gt[x][i], ok);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d", &n,&m);
    for (int i = 1; i<=m; ++i)
    {
        scanf("%d %d", &x,&y);
        g[x].pb(y);
        gt[y].pb(x);
    }
    for (int i = 1; i<=n; ++i)
        if (!sel[i])
            df1(i);
    memset(sel,false,sizeof(sel));
    for (int i = N ; i>=1; --i)
        if (!sel[st[i]])
        {
            ++ret;
            df2(st[i], false);
        }
    memset(sel,false,sizeof(sel));
    printf("%d\n", ret);
    for (int i = N; i>=1; --i)
        if (!sel[st[i]])
        {
            df2(st[i],true);
            printf("\n");
        }
    return 0;
}