Cod sursa(job #3272884)

Utilizator CiubarLoverBaiatu cu Ciubaru CiubarLover Data 31 ianuarie 2025 12:26:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> edge[100005];

int n,m;
int x,y;
bool visited[100005];

int main() {

    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    int counter = 0;
    for (int i=1;i<=n;i++) {
        if (visited[i]) {
            continue;
        }
        counter++;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            x = q.front();
            q.pop();
            visited[x] = true;
            for (int j=0;j<edge[x].size();j++) {
                if (!visited[edge[x][j]]) {
                    q.push(edge[x][j]);
                    visited[edge[x][j]] = true;
                }
            }
        }
    }
    fout << counter;
    return 0;
}