Cod sursa(job #2933592)

Utilizator CrisanelCrisan Alexandru Crisanel Data 5 noiembrie 2022 11:57:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>


using namespace std;

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

vector<int> v[100001];
int n, m;
int ans[100001];

bool viz[100001];


void afisare () {
    for(int i = 1;  i <= n; ++ i)
        out << ans[i] << ' ';
}

// BFS
void bfs(int sp) {
    queue<int> q;
    q.push(sp);

    while(!q.empty()) {
        int nod_current = q.front();
        q.pop();
        for(auto vecin: v[nod_current]) {
            if(ans[vecin] == -1) {
                ans[vecin] = ans[nod_current] + 1;
                q.push(vecin);
            }
        }
    }
}

// DFS
void dfs(int sp) {
    viz[sp] = 1;
    for(auto vecin: v[sp])
        if (!viz[vecin])
            dfs(vecin);
}

int main() {
    int t, s;
    int nr_comp = 0;


    //afisare();


    in >> n >> m;

    for(int i = 0; i < m ; ++ i) {
        int x, y;
        in >> x >> y;
        v[x].push_back(y) ;
        v[y].push_back(x);
    }

    for(int i = 1; i <= n; ++ i) {
        if(!viz[i]) {
            nr_comp ++;
            dfs(i);
        }
    }
    //ans[i] = -1;

    //ans[s] = 0;
    //dfs(s);
    out << nr_comp;
    //afisare();

    return 0;
}