Cod sursa(job #406795)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 1 martie 2010 20:10:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>s
#define size 100010

using namespace std;

struct nod
{
    int inf;
    nod *next;
}*a[size],*rez[size],*at[size];

int n,m;
int nr_rez;
int viz[size];
int sir[size];
int nr;

void add(nod *&A,int a)
{
    nod *q=new nod;
    q->inf=a;
    q->next=A;
    A=q;
}

void citire()
{
    int n1,n2;
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf("%d %d",&n1,&n2);
        add(a[n1],n2);
        add(at[n2],n1);
    }
}

void df(int n)
{
    viz[n]=1;
    for (nod *q=a[n];q;q=q->next)
        if (!viz[q->inf])
            df(q->inf);
    sir[nr++]=n;
}

void df2(int n)
{
    viz[n]=0;
    add(rez[nr_rez],n);
    for (nod *q=at[n];q;q=q->next)
        if (viz[q->inf])
            df2(q->inf);
}

void solve()
{
    for (int i=1;i<=n;i++)
        if (!viz[i])
            df(i);
    for (int i=n-1;i>=0;i--)
        if (viz[sir[i]])
        {
            df2(sir[i]);
            nr_rez++;
        }
}

void afish()
{
    printf("%d\n",nr_rez);
    for (int i=0;i<nr_rez;i++)
    {
        for (nod *j=rez[i];j;j=j->next)
            printf("%d ",j->inf);
        printf("\n");
    }
}

int main ()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    citire();
    solve();
    afish();
    return 0;
}