Cod sursa(job #1520226)

Utilizator tc_iuresiures tudor-cristian tc_iures Data 8 noiembrie 2015 15:18:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int Nmax = 100005;

int N, M, nrECon;
vector<int> G[Nmax];
bool used[Nmax];

void read()
{
   ifstream f("dfs.in");
   f >> N >> M;
   for(int i = 0; i < M; i ++)
   {
      int x, y;
      f >> x >> y;
      G[x].push_back(y);
      G[y].push_back(x);
   }
   f.close();
}

void DFS(int Node)
{
   used[Node] = true;
   for(int i = 0; i < G[Node].size(); i ++)
   {
      int Ngh = G[Node][i];
      if(!used[Ngh])
      {
         DFS(Ngh);
      }
   }
}

void solve()
{
    for(int i = 1; i <= N; i ++)
    {

      if(!used[i])
      {
         nrECon ++;
         DFS(i);
      }
    }
}

void print()
{
   ofstream g("dfs.out");
   g << nrECon;
   g.close();
}

int main()
{
    read();
    solve();
    print();
    return 0;
}