Cod sursa(job #1905447)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 6 martie 2017 08:08:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout("dfs.out");

bool viz[100009];
int n, m, cnt;
vector <int> L[100009];

void Citire()
{
   int x, y;
   fin >> n >> m;
   for (int i=1; i<=m; i++)
   {
      fin >> x >> y;
      L[x].push_back(y);
      L[y].push_back(x);
   }
}

void DFS(int k)
{
  int i, j;
  viz[k]=1;

  for (j=0; j<L[k].size(); j++)
      if (!viz[L[k][j]])
         DFS(L[k][j]);
}

void Rezolva()
{
  int i, j;
  for (i=1; i<=n; i++)
  {
    if (!viz[i]) 
     {
        DFS(i);    
        cnt++;
     }
  }
  fout << cnt << "\n";
}

int main ()
{
  Citire();
  Rezolva();
  fin.close();
  fout.close();
  return 0;
}