Cod sursa(job #1356892)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 23 februarie 2015 17:20:18
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct lista{int nod; lista *leg;} *G[501],*TG[501];
int n,m,U[501],F[501],ok;
void adaug(int i,int j)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->leg=G[i];
    G[i]=p;
}
void transadaug(int i,int j)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->leg=TG[i];
    TG[i]=p;
}
void citire()
{
    f>>n>>m;
    int i,j;
    while(m--)
    {
        f>>i>>j;
        adaug(i,j);
        transadaug(j,i);
    }
}
void DFS(int s)
{
    lista *p;
    U[s]=1;
    for(p=G[s];p;p=p->leg)
        if(!U[p->nod])
    {
        DFS(p->nod);
    }
    F[++F[0]]=s;
}
void DFS2(int s)
{
    lista *p;
    U[s]=1;
    if(!ok) g<<s<<" ";
    for(p=TG[s];p;p=p->leg)
        if(!U[p->nod])
    {
       // g<<p->nod<<'\n';
        DFS2(p->nod);
    }
}
int main()
{
    citire();
    for(int i=1;i<=n;++i)
        if(!U[i]) DFS(i);
    memset(U,0,sizeof U);
    int nr=0; ok=1;
    for(int i=n;i>=1;--i)
      {
         if(!U[F[i]])
            {  DFS2(F[i]);
                nr++;
            }
      }
     memset(U,0,sizeof U);
     g<<nr<<'\n'; ok=0;
     for(int i=n;i>=1;--i)
      {
         if(!U[F[i]])
            {  DFS2(F[i]);
               g<<'\n';
            }
      }
    return 0;
}