Cod sursa(job #2796296)

Utilizator Alex18maiAlex Enache Alex18mai Data 7 noiembrie 2021 20:52:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.73 kb
/*
Alexandru Enache
Grupa 252
*/

#include <bits/stdc++.h>
using namespace std;

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

class Graph{

private:

    int m_nodes;
    vector < vector < int > > m_gr;

    void dfs(int node, vector < bool > &used){
        used[node] = true;
        for (auto &x: m_gr[node]){
            if (!used[x]){
                dfs(x, used);
            }
        }
    }

    void dfs_biconexe (int nod , int dad, vector < int > &lv, vector < int > &MIN, stack < int > &s, vector < vector < int > > &ans){
        lv[nod] = lv[dad]+1;
        MIN[nod] = lv[nod];
        s.push(nod);
        for (auto &x : m_gr[nod]){
            if (lv[x]){
                if (x != dad){
                    MIN[nod] = min(MIN[nod] , lv[x]);
                }
            }
            else{
                dfs_biconexe(x , nod, lv, MIN, s, ans);
                MIN[nod] = min(MIN[nod] , MIN[x]);
                if (MIN[x] >= lv[nod]){
                    vector < int > aux;
                    while (s.top() != x){
                        aux.push_back(s.top());
                        s.pop();
                    }
                    aux.push_back(x);
                    s.pop();
                    aux.push_back(nod);
                    ans.push_back(aux);
                }
            }
        }
    }

    void dfs_ctc(int nod, vector < vector < int > > &gr, vector < bool > &used, vector < int > &aux){
        used[nod] = true;
        for (auto& x : gr[nod]) {
            if (!used[x]) {
                dfs_ctc(x, gr, used, aux);
            }
        }
        aux.push_back(nod);
    }

public:

    Graph(){
        m_nodes = 0;
        m_gr = {};
    }

    Graph(int nodes, vector < vector < int > > &gr){
        m_nodes = nodes;
        m_gr = gr;
    }

    vector < int > bfs(int start){
        queue < int > q;
        vector < int > dist(m_nodes + 1, -1);

        dist[start] = 0;
        q.push(start);

        while (!q.empty()){
            int now = q.front();
            q.pop();

            for (auto &x : m_gr[now]){
                if (dist[x] == -1){
                    dist[x] = dist[now] + 1;
                    q.push(x);
                }
            }
        }

        return dist;
    }

    int comp_conexe(){

        int cont = 0;
        vector < bool > used(m_nodes + 1, false);
        for (int i=1; i<=m_nodes; i++){
            if (!used[i]){
                dfs(i, used);
                cont++;
            }
        }

        return cont;
    }

    vector < vector < int > > comp_biconexe(){

        vector < vector < int > > ans;

        vector < int > lv (m_nodes + 1, 0);
        vector < int > MIN (m_nodes + 1, 0);
        stack < int > s;

        for (int i=1; i<=m_nodes; i++){
            if (!lv[i]){
                dfs_biconexe(i , 0, lv, MIN, s, ans);
                while (!s.empty()) s.pop();
            }
        }

        return ans;
    }

    vector < vector < int > > ctc(){

        vector < vector < int > > ans;

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

        reverse(ord.begin(), ord.end());

        vector < vector < int > > inv(m_nodes + 1);

        for (int i=1; i<=m_nodes; i++){
            used[i] = false;
            for (auto &x : m_gr[i]){
                inv[x].push_back(i);
            }
        }

        for (auto &x: ord){
            if (!used[x]){
                vector < int > aux;
                dfs_ctc(x, inv, used, aux);
                ans.push_back(aux);
            }
        }

        return ans;
    }

    vector < int > ord_topologica(){

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

        reverse(ord.begin(), ord.end());

        return ord;
    }

    bool Havel_Hakimi(vector < int > v){

        for (int i=0; i<v.size(); i++){
            sort(v.begin(), v.end());
            reverse(v.begin(), v.end());

            if (v[0] > (int)v.size()-1) return false;

            for (int j=1; j<=v[0]; j++){
                v[j]--;
                if (v[j] < 0) return false;
            }
            v[0] = 0;
        }

        return true;
    }

};


void solve() {

    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    fin>>n>>m;

    vector < vector < int > > gr(n+1);

    for (int i=1; i<=m; i++){
        int a, b;
        fin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    Graph graph = Graph(n, gr);

    int comp_conexe = graph.comp_conexe();

    fout<<comp_conexe<<'\n';

}


int main() {

    solve();

    return 0;
}