Cod sursa(job #2494362)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 17 noiembrie 2019 19:18:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

bitset <100001> ok;
vector <int> v[100001];

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

void dfs(int nod)
{
  ok[nod]=1;
  int x;
  for (int i=0;i<v[nod].size();i++)
  {
    x=v[nod][i];
    if (ok[x]==0)
      dfs(x);
  }
}

int main()
{
    int n,m,conexe=0,a,b;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
      in>>a>>b;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    for (int i=1;i<=n;i++)
    {
      if (!ok[i])
        conexe++,dfs(i);
    }
    out<<conexe;
    return 0;
}