Cod sursa(job #463050)

Utilizator giuliastefGiulia Stef giuliastef Data 14 iunie 2010 14:18:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod{
       int info;
       nod *next;
       } *vecini[100005];
int n,m,viz[100005];
void add(nod *&prim, int val)
{
     nod *p=new nod;
     p->info=val;
     p->next=prim;
     prim=p;
}
void citire()
{
     int i,x,y;
     f>>n>>m;
     for(i=1;i<=m;i++)
     {
      f>>x>>y;
      add(vecini[x],y);
      add(vecini[y],x);
     }
     f.close();
}
void dfs(int nodul)
{
     nod *p;
     viz[nodul]=1;
     for(p=vecini[nodul];p;p=p->next)
      if(!viz[p->info])
       dfs(p->info);
}
int main()
{
    int i,cnt=0;
    citire();
    for(i=1;i<=n;i++)
     if(!viz[i])
     {
                cnt++;
                dfs(i);
     }
    g<<cnt<<"\n";
    g.close();
    return 0;
}