Cod sursa(job #628631)

Utilizator attila3453Geiszt Attila attila3453 Data 1 noiembrie 2011 19:02:56
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <stdio.h>

using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

struct nod
{
	vector<int> frati;
	bool viz;
};

int n, m, ncc;
vector<nod> noduri;

void citire () {
  int i, x, y;

  fi >> n >> m;
  
  nod Nod;
  Nod.viz = false;
  
  for(i = 0;i < n;i++)
	  noduri.push_back(Nod);
  
  for (i = 1; i <= m; i++) {
    fi >> x >> y;
    
    noduri[x].frati.push_back(y);
    noduri[y].frati.push_back(x);//necesar?
  }
}

void dfs(int start)
{
	vector<nod> stack;
	stack.push_back(noduri[start]);	
	nod top;
	unsigned int i;
	
	while(!stack.empty())
	{
		top = stack.back();
		stack.pop_back();
		top.viz = true;
		
		for(i = 0;i<top.frati.size();i++)
			noduri[top.frati[i]].viz = true;
			
		top.viz = false;
	}
}

int main () {
  int i;

  citire();
  for (i = 1; i <= n; i++)
    if (!noduri[i].viz) 
    {
      ncc++;      
      dfs(i);
    }
    
  fo << ncc;
  return 0;
}