Cod sursa(job #2795140)

Utilizator redikusTiganus Alexandru redikus Data 6 noiembrie 2021 00:14:21
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.81 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, stack<pair<int, int>>& s, int& timpcurent, vector<string>& rasp){
        timpcurent++;
        timp[tata]=timpcurent;
        rev[tata]=timpcurent;
        for(int fiu:adiacenta[tata]){
            if(timp[fiu]==-1){
                s.push(make_pair(tata, fiu));
                dfsbiconex(fiu, timp, rev, 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;
                    string str="";
                    aux.insert(stop.first);
                    aux.insert(stop.second);
                    str+=to_string(stop.first);
                    str+=" ";
                    str+=to_string(stop.second);
                    str+=" ";
                    while(s.top() != stop){
                        int nodcur = s.top().first;
                        if(aux.find(nodcur)==aux.end()){
                            str+=to_string(nodcur);
                            str+=" ";
                            aux.insert(s.top().first);
                        }
                        s.pop();
                    }
                    str+='\n';
                    rasp.push_back(str);
                    s.pop();
                }
            }
            else{
                rev[tata] = min(rev[tata], timp[fiu]);
                if(timp[fiu] < timp[tata]){
                    s.push(make_pair(tata, fiu));
                }
            }
        }
    }

    vector<string> biconex(){
        vector<int> timp(noduri+1, -1), rev(noduri+1);
        stack<pair<int, int>> s;
        vector<string> 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, s, timpo, rasp);
            }
            if(!s.empty()){
                unordered_set<int> aux;
                string str;
                while(!s.empty()){
                    if(aux.find(s.top().first)==aux.end()){
                        aux.insert(s.top().first);
                        str+=to_string(s.top().first);
                        str+=" ";
                    }
                    if(aux.find(s.top().second)==aux.end()){
                        aux.insert(s.top().second);
                        str+=to_string(s.top().second);
                        str+=" ";
                    }
                    s.pop();
                }
                str+='\n';
                rasp.push_back(str);
            }
        }
        return rasp;
    }

};

int main(){

    ifstream in("biconex.in");
    ofstream out("biconex.out");
    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<string> fin = x.biconex();
    out<<fin.size()<<'\n';
    for(string i:fin){
        out<<i;
    }
    return 0;
}