Cod sursa(job #3333788)

Utilizator zionlyismAdobroaiei David zionlyism Data 15 ianuarie 2026 09:41:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>

#define NMAX 100001

using namespace std;

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

int n, m;
vector<int> A[NMAX];

int cc[NMAX]; //cc[i] = numarul comp. conexei in care este nodul i

int nrc = 0; //nr de comp conexe

void citire();
void DFS(int k);

int main()
{
    int i, j;
    citire();
    for(i = 1; i <= n; i++)
        if(cc[i] == 0)
        {
            nrc++;
            DFS(i);
        }
    fout<<nrc<<'\n';
    return 0;
}

void citire()
{
 int i, x, y;
 fin>>n>>m;
 for(i = 0; i < m; i++)
 {
     fin>>x>>y;
     A[x].push_back(y);
     A[y].push_back(x);
 }
}

void DFS(int k)
{
 int i;
 cc[k] = nrc;
 for(i = 0; i < A[k].size(); i++)
    if(!cc[A[k][i]])
       DFS(A[k][i]);
}