Cod sursa(job #2650983)

Utilizator patriciaxdBraica Patricia patriciaxd Data 21 septembrie 2020 11:45:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int N,M,k;
bool Vizitat[nmax];
vector <int> Muchii[nmax];
void dfs(int Nod)
{ Vizitat[Nod]=true;
  for(size_t i=0;i<Muchii[Nod].size();i++)
  { int Vecin=Muchii[Nod][i];
    if(!Vizitat[Vecin])
        dfs(Vecin);
  }
}
void citire()
{ in>>N>>M;
  for(int i=1;i<=M;i++)
  { int x,y;
      in>>x>>y;
      Muchii[x].push_back(y);
      Muchii[y].push_back(x);
  }
}
int main()
{ citire();
  dfs(1);
  k++;
for(int i=1;i<=N;i++)
{ if(!Vizitat[i])
    {dfs(i);
    k++;
    }
}
out<<k;
in.close();
out.close();

    return 0;
}