Cod sursa(job #1638732)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 8 martie 2016 08:52:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

vector <int> L[100009];
int N, M, cnt, viz[100009];

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

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

void Rezolva()
{
   int i;
   cnt = 0;
   for (i=1; i<=N; i++)
     if (viz[i] == 0)
        {
           cnt++;
           DFS(i);
        }
}


int main ()
{
  Citire();
  Rezolva();
  fout << cnt << "\n";
  fin.close();
  fout.close();
  return 0;
}