Cod sursa(job #304435)

Utilizator cvicentiuCiorbaru Vicentiu Marian cvicentiu Data 13 aprilie 2009 08:51:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>   
int n,m;   
int nr;   
struct nod {   
        int x;   
        nod *urm;   
};   
bool viz[200001];   
nod *vf[100001];   
  
using namespace std;   
void adauga(int ex1,int ex2){   
    nod *p=new nod;   
    nod *q=new nod;   
    p->urm = vf[ex1];   
    p->x = ex2;   
    vf[ex1]=p;   
    q->urm = vf[ex2];   
    q->x = ex1;   
    vf[ex2]=q;   
}   
  
void citire(){   
    int ex1,ex2;   
    fstream fin("dfs.in",ios::in);   
    fin>>n>>m;   
    for (int i=1;i<=m;i++){   
        fin>>ex1>>ex2;   
        adauga(ex1,ex2);   
    }   
    fin.close();   
}   
  
void dfs(int x){   
    nod *p;   
    viz[x]=true;   
    for (p=vf[x];p!=NULL;p=p->urm){   
        if (viz[p->x]==false)   
            dfs(p->x);   
    }   
}   
  
int main(){   
    fstream fout("dfs.out",ios::out);   
    citire();   
    for (int i=1;i<=n;i++){   
        if (viz[i]==false){   
            nr++;   
            dfs(i);   
        }   
    }   
    fout<<nr;   
    fout.close();   
return 0;   
}