Cod sursa(job #390013)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 2 februarie 2010 18:48:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<fstream>
#define inf "ctc.in"
#define outf "ctc.out"
#define NMax 100010
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

struct graf
{
int nod;
graf *next;
};

struct lista
{
int varf;
lista *next;
};

int N,M;
int nr,nrc;
int postordine[NMax];
int viz[NMax];
graf *a[NMax];
graf *at[NMax];
lista *com[NMax];

void add(int x,int y,graf *v[])
{
graf *t=new graf;
t->nod=y;
t->next=v[x];
v[x]=t;
}

void Citire()
{
int x,y;
f>>N>>M;
for(int i=1;i<=M;i++)
    {
    f>>x>>y;
    add(x,y,a);
    add(y,x,at);
    }
}

void DFS(int s)
{
viz[s]=1;
graf *t=a[s];
while(t)
    {
    if(!viz[t->nod])DFS(t->nod);
    t=t->next;
    }
postordine[++nr]=s;
}

void addl(int nrc,int s)
{
lista *t=new lista;
t->varf=s;
t->next=com[nrc];
com[nrc]=t;
}

void DFST(int s)
{
viz[s]=0;
addl(nrc,s);
graf *t=at[s];
while(t)
    {
    if(viz[t->nod])DFST(t->nod);
    t=t->next;
    }
}

void Rezolvare()
{
//parcurgem graful si punem nodurile in postordine
for(int i=1;i<=N;i++)
    if(!viz[i])DFS(i);
//parcurgem grafurl transpus prelucand nodurile in postordine
for(int i=N;i>0;i--)
    {
    if(viz[postordine[i]])
        {
        nrc++;
        DFST(postordine[i]);
        }
    }
g<<nrc<<"\n";
lista *t;
for(int i=1;i<=nrc;i++)
    {
    t=com[i];
    while(t)
        {
        g<<t->varf<<" ";
        t=t->next;
        }
    g<<"\n";
    }
}

int main()
{
Citire();
Rezolvare();
f.close();
g.close();
return 0;
}