Cod sursa(job #3185266)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 18 decembrie 2023 17:15:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>
#define DIM 100001

using namespace std;

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

int found[DIM];

vector <int> G[DIM];

int n, i, Q, x, y, answer;

void dfs(int node){

    found[node] = 1;

    for(int i = 0 ; i < G[node].size(); i++)

        if(!found[G[node][i]])

            dfs(G[node][i]);

}

int main(){

    fin >> n >> Q;

    while(Q--){

        fin >> x >> y;

        G[x].push_back(y);

        G[y].push_back(x);

    }

    for(i=1;i<=n;i++)

        if(!found[i]){

            dfs(i);

            answer++;

        }

    fout << answer << "\n";

}