Cod sursa(job #628630)

Utilizator attila3453Geiszt Attila attila3453 Data 1 noiembrie 2011 19:01:25
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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?
  }
}

int main () {
  int i;

  citire();
  for (i = 1; i <= n; i++)
    if (!noduri[i].viz) 
    {
      ncc++;
      
      vector<nod> stack;
	  stack.push_back(noduri[i]);	
	  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;
	  }
    }
    
  fo << ncc;
  return 0;
}