Cod sursa(job #1568861)

Utilizator asavoaeigeoAsavoaei Georgiana asavoaeigeo Data 14 ianuarie 2016 19:39:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#define N 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[N],timp[N],nrcomp;
struct nod
{
  int info;
  nod *urm;
};
nod *G[N], *Gt[N];

void Add(nod*&prim, int x)
{
    nod *q=new nod;
    q->info=x;
    q->urm=prim;
    prim=q;
}

void Citire()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        Add(G[x],y);
        Add(Gt[y],x);
    }
}

void DFS(int x)
{
    viz[x]=1;
    for(nod *p=G[x];p!=NULL;p=p->urm)
      if(viz[p->info]==0) DFS(p->info);
    timp[++timp[0]]=x;  
}

void DFST(int x)
{
    viz[x]=0;
    for(nod *p=Gt[x];p!=NULL;p=p->urm)
      if(viz[p->info]==1) DFST(p->info);
}

void DFS_T(int x)
{
    viz[x]=0; 
    fout<<x<<" ";
    for(nod *p=Gt[x];p!=NULL;p=p->urm)
      if(viz[p->info]==1) DFS_T(p->info);
    
}
int main()
{
    Citire();
    for(int i=1;i<=n;i++)
      if(viz[i]==0) DFS(i);
    for(int i=n;i>=1;i--)
      if(viz[timp[i]]==1) {
                           nrcomp++;
                           DFST(timp[i]);
                          }
    fout<<nrcomp<<"\n";
    for(int i=1;i<=n;i++) viz[i]=1;                      
    for(int i=n;i>=1;i--)
      if(viz[timp[i]]==1) {
                           DFS_T(timp[i]);
                           fout<<"\n";
                          }                      
    return 0;
}