Cod sursa(job #2783021)

Utilizator redikusTiganus Alexandru redikus Data 13 octombrie 2021 17:45:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

class graf{

    int noduri, muchii;
    vector<vector<int>> adiacenta;

public:
    graf(vector<vector<int>> a, int b, int c): adiacenta(a), noduri(b), muchii(c) {};

    vector<int> bfs(int start){
        vector<int> res(this->adiacenta.size(), -1);
        vector<int> vis(this->adiacenta.size());
        queue<int> q;
        vis[start] = 1;
        q.push(start);
        res[start] = 0;
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            for(int i:adiacenta[curr]){
                if(vis[i] == 0){
                    vis[i] = 1;
                    q.push(i);
                    res[i] = res[curr]+1;
                }
            }
        }
        return res;
    }

    int dfs(){
        vector<int> vis(this->noduri);
        int res = 0;
        stack<int> s;
        for(int i=0; i<this->noduri; i++){
            if(vis[i] == 0){
                res++;
                vis[i]=1;
                s.push(i);
                while(!s.empty()){
                    int curr = s.top();
                    s.pop();
                    for(int i=adiacenta[curr].size()-1; i>=0; i--){
                        int nod = adiacenta[curr][i];
                        if(vis[nod] == 0){
                            vis[nod] = 1;
                            s.push(nod);
                        }
                    }
                }
            }
        }
        return res;
    }

};

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

int main(){

    int n, m;
    in>>n>>m;
    vector<vector<int>> mat(n);
    for(int i=0; i<m; i++){
        int aux1, aux2;
        in>>aux1>>aux2;
        mat[aux1-1].push_back(aux2-1);
        mat[aux2-1].push_back(aux1-1);
    }
    graf x(mat, n, m);
    out<<x.dfs();
    return 0;
}