Cod sursa(job #650620)

Utilizator cippyApetrei Ciprian cippy Data 18 decembrie 2011 16:03:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
typedef struct nod* lst; struct nod {int nd; lst next;};
vector<int>vecini[100005];
int viz[100005];
int m,n;


void df(int nod){
     int nr;
	viz[nod]=1;
	for(int i=0;i<vecini[nod].size();i++) 
	{    nr=vecini[nod][i];
		if(viz[nr]==0) df(nr);
    }
}
void citire(){
     freopen("dfs.in","r",stdin);
     freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
		int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		vecini[a].push_back(b);
		vecini[b].push_back(a);
	}
}
int main(){
	int nr=0;
	citire();
	int i;
	for(i=1;i<=n;i++)
		if(viz[i]==0) nr++,df(i);
	printf("%d\n",nr);
	return 0;
}