Cod sursa(job #1614230)

Utilizator GabiADAndrei Gabriel GabiAD Data 25 februarie 2016 21:05:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector <vector <int>> graph;
vector <int> visited;
unsigned int n, m;


void DFS(unsigned int vertex)
{
  
  if(vertex < 0 || vertex > n-1)
    return;

  stack <int> s;
  int element;
  bool found;
  unsigned int i;

  s.push(vertex);

  visited[vertex] = true;

  while(!s.empty())
    {
      element = s.top();
      found = false;
      
      for (i = 0; i < graph[element].size() && !found; i++)
	{
	  if(!visited[graph[element][i]])
	    {
	      found = true;

	    }

	}
	  
	  if(found)
	    {
	       i--;
	      s.push(graph[element][i]);

	      visited[graph[element][i]] = true;

	    }
	  else
	    s.pop();
	  
	
    }


}


int main()
{
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);
  
  cin >> n >> m;
  graph.resize(n);

  visited.resize(n, false);

  int x, y;
  unsigned int i;

  for (i = 0; i < m; i++)
    {
      cin >> x >> y;

      x--;
      y--;

      graph[x].push_back(y);
      graph[y].push_back(x);
    }

  int rez = 0;
  
  for (i = 0; i < visited.size() && i < n; i++)
    if(!visited[i])
      {
	DFS(i);
	rez++;
      }

  cout << rez;
  
  return 0;
}