Cod sursa(job #3193938)

Utilizator ciupeiCiupei Matei ciupei Data 16 ianuarie 2024 10:11:07
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

int const NMAX = 100005;

vector <int> G[NMAX];
queue <int> q;

int n,m,s;
int x,y;

int dad[NMAX];
int dist[NMAX];
bool viz[NMAX];

void DFS(int nod)
{
    viz[nod] = 1;
    for(int nbr: G[nod])
    {
        if(!viz[nbr])
        {
            DFS(nbr);
        }
    }
}

int main()
{
   fin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       fin>>x>>y;
       G[x].push_back(y);
       G[y].push_back(x);
   }
   int cc = 0;
   for(int i=1;i<=n;i++)
   {
       if(!viz[i])
       {
           DFS(i);
           cc++;
       }
   }
   cout<<cc;
   return 0;
}