Cod sursa(job #671246)

Utilizator handz.FMI Andrei Tanasescu handz. Data 30 ianuarie 2012 23:17:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#define maxN 100005
#define maxM 200005
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,ST[maxN],nr=0,saw[maxN],nr_cc=0;

struct list
{
    int nod;
    list *next;
} *G[maxN],*GT[maxN];

struct list_cc
{
    int nod;
    list_cc *next;
} *Lcc[maxN];

void addN(int x,int y)
{
    list *p,*q;

    q=new list;
    q->nod=y;
    q->next=G[x];
    G[x]=q;

    p=new list;
    p->nod=x;
    p->next=GT[y];
    GT[y]=p;
}

void reset_saw()
{
    for(int i=1; i<=n ;i++)
        saw[i]=0;
}

void read_ini()
{
    f>>n; f>>m;
    int i,a,b;
    for(i=1; i<=m ;i++)
    {
        f>>a; f>>b;
        addN(a,b);
    }
    reset_saw();
}

void DFg(int s)
{
    list *p;
    saw[s]=1;
    for(p=G[s]; p!=NULL ;p=p->next)
    {
        if(!saw[p->nod])
            DFg(p->nod);
    }
    ST[nr++]=s;
}

void DFgt(int s)
{
    list *q;
    list_cc *p;

    p=new list_cc;
    p->nod=s;
    p->next=Lcc[nr_cc];
    Lcc[nr_cc]=p;

    saw[s]=1;

    for(q=GT[s]; q!=NULL ;q=q->next)
    {
        if(!saw[q->nod])
            DFgt(q->nod);
    }
}

void print_cc()
{
    int i;
    list_cc *q;
    g<<nr_cc<<"\n";
    for(i=1; i<=nr_cc ;i++)
    {
        q=Lcc[i];
        while(q)
        {
            g<<q->nod<<" ";
            q=q->next;
        }
        g<<"\n";
    }
}

int main()
{
    read_ini();
    int i;
    for(i=1; i<=n ;i++)
    {
        if(!saw[i])
            DFg(i);
    }
    reset_saw();
    for(i=n-1; i>=0 ;i--)
    {
        if(!saw[ST[i]])
        {
            nr_cc++;
            DFgt(ST[i]);
        }
    }
    print_cc();
    return 0;
}