Cod sursa(job #209974)

Utilizator catalina5catalina serban catalina5 Data 25 septembrie 2008 21:21:14
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
using namespace std;
long n,m;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod {
    int info;
    nod *urm;
};
typedef struct nod nod;
nod *v[100002];
int viz[100002];
void add(int x,int y) {
    nod *q=new nod;
    q -> info=x;
    q -> urm=v[y];
    v[y]=q;
}
void DFS(int x) {
    viz[x]=1;
    //cout<<v[x]->info;
    for(nod *q=v[x];q;q=q->urm)
        if(viz[q->info]==0)
            DFS(q->info);
}
int parcurgere() {
	int x=0;
    for(int i=0;i<=n;i++)
	if(viz[i]==0){
	    DFS(i);
	    x++;
	}
	return x;
}
void citire() {
     int x,y;
     fin>>n>>m;
     for(int i=0;i<m;i++) {
        fin>>x>>y;
        add(x,y);
        add(y,x);
     }
}
int main() {
     citire();
     fout<<parcurgere()<<"\n";
	return 0;
}