Cod sursa(job #811181)

Utilizator daniel11daniel fratila daniel11 Data 11 noiembrie 2012 17:30:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <string.h>
using namespace std;
struct nod
{
    int info;
    nod *urm;
};
nod *l[100001],*p;
int viz[100001];
int nr,n,m,x,y,i;

void dfs (int x)
{
    nod *c;
    viz[x]=1;
    c=new nod; c=l[x];
    while (c)
    {
        if (!viz[c->info])
        {
            dfs(c->info);
        }
        c=c->urm;
    }
}
int main()
{
   ifstream f("dfs.in");
   ofstream g("dfs.out");
   f>>n>>m;
   memset(l,NULL,sizeof(l));
   for (i=1;i<=m;i++)
   {
       f>>x>>y;
       p=new nod;
       p->info=y;
       p->urm=l[x];
       l[x]=p;
       p=new nod;
       p->info=x;
       p->urm=l[y];
       l[y]=p;
   }
for (i=1;i<=n;i++)
 if (!viz[i])
  dfs(i),nr++;
 g<<nr<<'\n';
 return 0;
}