Cod sursa(job #2556907)

Utilizator federicisFedericis Alexandru federicis Data 25 februarie 2020 12:06:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;

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

vector<int> muchii[nmax];


unsigned long long n,m,ins=0;
bool vizitat[nmax];


void DFS(int nod)
{  int nr=0;
while(nr+1<=muchii[nod].size())
{ if(!vizitat[muchii[nod][nr]])
   {
       vizitat[muchii[nod][nr]]=1;
       DFS(muchii[nod][nr]);
   }
   nr++;
}


}

int main()
{
  in>>n>>m;
  for(int i=1;i<=m;i++)
  {
      int a,b;
      in>>a>>b;
      muchii[a].push_back(b);
      muchii[b].push_back(a);
  }
  for(int i=1;i<=n;i++)
  {
      if(!vizitat[i])
      { vizitat[i]=1;
          DFS(i);
        ins++;
      }
  }
  out<<ins;

    return 0;
}