Cod sursa(job #1110265)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 17 februarie 2014 21:53:56
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
using namespace std;
 

ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m;///numarul de noduri;
int viz[1066];/// vectorul de noduri vizate ( daca am mai fost in nodul V atunci viz[V]=1 , altfel viz[V]=0
int H[1066][1066];/// matricea de muchii H[i][j] este egal cu  1 daca am muchie intre i si j alfel e 0
int numar_comp; ///numarul de componente conexe (rezultatul)

void dfs(int X) ///sunt in nodul X cu dfs-ul
{
	viz[X]=1; /// marchez Nodul X ca fiind vizat
	int i;/// atentie i este declarat local adica in functie ,daca il declari global nu se revine bine din recursivitate
	
	for(i=1;i<=n;++i) 
		if (H[X][i]==1) /// daca am muchie de la Nodul X la Nodul i
		  if (viz[i]==0) /// tot timpul ma duc intrun Nod care nu a mai fost vizat deja
		  {
			  dfs(i); /// ma mut cu dfs-ul in nodul i;
			  ///dupa ce se apeleaza functia dfs(i) se revine recursiv in nodul X (seamana cu backtrackingu)
		  }
}

int main()
{
	///citesc numarul de noduri, numarul de muchii si muchiile dintre ele , daca H[i][j] e 1 am muchie intre nodul i si j
	f>>n>>m;
	int i;
	
	for(i=1;i<=m;++i)
	{
	   int xx,yy;
	   f>>xx>>yy;
	   ///graful e noerientat daca am muchie de la i la j am si de la j la i
	   H[xx][yy]=1;
	   H[yy][xx]=1;
	}
	
	
	for(i=1;i<=n;++i)
		if (viz[i]==0) /// daca nodul i face dintro componenta conexa noua adica nu a mai fost vizat inainte
		{
		   ++numar_comp;
		   dfs(i);
		}
	
    g<<numar_comp<<'\n';
		
	return 0;
}