Cod sursa(job #729736)

Utilizator OwnedCheciches Marius Owned Data 29 martie 2012 21:49:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
using namespace std;

#define maxn 100001

int s[maxn],n,m,viz[maxn],c,u,b[maxn];
vector <int> a[maxn];

void dfs(int nod){
	int i;
	s[u]=nod;
	viz[nod]=1;
	for(i=0;i<b[nod];i++)
		if(viz[a[nod][i]]==0){
			u++;
			dfs(a[nod][i]);}
	u--;}

int main(){
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	f>>n>>m;
	int i,x,y;
	for(i=1;i<=m;i++){
		f>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);}
	for(i=1;i<=n;i++)
		b[i]=a[i].size();
	for(i=1;i<=n;i++)
		if(viz[i]==0){
			c++;
			u++;
			dfs(i);}
	g<<c;
	f.close();
	g.close();
	return 0;}