Cod sursa(job #3333488)

Utilizator ioan19Buzdugan Ioan-Michael ioan19 Data 13 ianuarie 2026 18:10:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

int N, M;
vector<int> adj[100005];
int v[100005], cnt;

bool muchie(int x, int y){
    for(int i = 0; i < adj[x].size(); i++)
        if(adj[x][i] == y)
            return true;
    return false;
}

void dfs(int i){
    v[i] = cnt;
    
    for(int j = 0; j < adj[i].size(); j++)
        if(v[adj[i][j]] == 0)
            dfs(adj[i][j]);
}

int main(){

    f >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for(int i = 1; i <= N; i++){
        if (!v[i]) {
            cnt++;
            dfs(i);
        }
    }

    g << cnt;

    return 0;
}