Cod sursa(job #398386)

Utilizator alex@ndraAlexandra alex@ndra Data 18 februarie 2010 16:52:36
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;

vector <int> A[1000];
int n, m, vizitat[1000];

void citire()
{
	int j,x,y;
	ifstream f("dfs.in");
	   f>>n>>m;
	   
	for(j=1;j<=m;j++)
	{
		f>>x>>y;
		A[x].push_back(y);
		A[y].push_back(x);
	}
	
	f.close();
}

void df(int nod)
{ 
int i, vecini;
	vizitat[nod]=1;
	vecini=A[nod].size();
	
	for(i=0;i<vecini;i++)
          if(vizitat[A[nod][i]]==0)
             df(A[nod][i]);
}
             
int main()
{
	citire();
	int k, nr=0;
	for(k=1;k<=n;k++)
		if(vizitat[k]==0)
		{
		  nr++;
		  df(k);
		}
	
	ofstream g("dfs.out");
	  g<<nr;
	g.close();
	
	return 0;
}