Cod sursa(job #2794485)

Utilizator redikusTiganus Alexandru redikus Data 4 noiembrie 2021 23:10:04
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.14 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;
    }
*/

    void dfsbiconex(int tata, vector<int>& timp, vector<int>& rev, vector<int>& parinte, stack<pair<int, int>>& s, int& timpcurent, vector<unordered_set<int>>& rasp){
        timpcurent++;
        timp[tata]=timpcurent;
        rev[tata]=timpcurent;
        for(int fiu:adiacenta[tata]){
            if(timp[fiu]==-1){
                s.push(make_pair(tata, fiu));
                parinte[fiu]=tata;
                dfsbiconex(fiu, timp, rev, parinte, s, timpcurent, rasp);
                rev[tata]=min(rev[tata], rev[fiu]);
                if((timp[tata]!=1 && rev[fiu]>=timp[tata]) || (timp[tata]==1 && adiacenta[tata].size()>1)){
                    pair<int, int> stop = make_pair(tata, fiu);
                    unordered_set<int> aux;
                    while(s.top() != stop){
                        aux.insert(s.top().first);
                        s.pop();
                    }
                    aux.insert(stop.first);
                    aux.insert(stop.second);
                    rasp.push_back(aux);
                    s.pop();
                }
            }
            else{
                rev[tata] = min(rev[tata], timp[fiu]);
                if(timp[fiu] < timp[tata]){
                    s.push(make_pair(tata, fiu));
                }
            }
        }
    }

    vector<unordered_set<int>> biconex(){
        vector<int> timp(noduri+1, -1), rev(noduri+1), parinte(noduri+1);
        stack<pair<int, int>> s;
        vector<unordered_set<int>> rasp;
        int timpo=0;
        //pt ca graful nu e neaparat conex trb sa facem de mai multe ori dfs
        for(int i=0; i<noduri; i++){
            if(timp[i]==-1){
                dfsbiconex(i, timp, rev, parinte, s, timpo, rasp);
            }
            if(!s.empty()){
                unordered_set<int> aux;
                while(!s.empty()){
                    aux.insert(s.top().first);
                    aux.insert(s.top().second);
                    s.pop();
                }
                rasp.push_back(aux);
            }
        }
        return rasp;
    }

};

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

int main(){

    int n, m;
    in>>n>>m;
    vector<vector<int>> mat(n+1);

    for(int i=0; i<m; i++){
        int aux1, aux2;
        in>>aux1>>aux2;
        mat[aux1].push_back(aux2);
        mat[aux2].push_back(aux1);
    }
    graf x(mat, n, m);
    vector<unordered_set<int>> fin = x.biconex();
    out<<fin.size()<<'\n';
    for(auto i:fin){
        for(int j:i){
            out<<j<<" ";
        }
        out<<'\n';
    }
    return 0;
}