Cod sursa(job #2680183)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 2 decembrie 2020 21:13:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
const int nmax=1e5;
struct edge{
    int u, v;
};
vector <edge> stk;
bool viz[nmax+2];
int low[nmax+2], tin[nmax+2];
int n, m, x, y;
int mom;
vector <vector <int> > comp;
vector <int> muchii[nmax+2];
void dfs(int nod, int par){
    viz[nod]=true;
    tin[nod]=low[nod]=++mom;
    int copii=0;
    for(auto &x:muchii[nod]){
        if(viz[x]==false){
            stk.push_back({nod, x});
            copii++;
            dfs(x, nod);
            if(low[x]>=tin[nod]){ ///adica nod e articulatie
                comp.push_back(vector<int>());
                while(!stk.empty()&&stk.back().u!=nod&&stk.back().v!=x){
                    comp.back().push_back(stk.back().v);
                    stk.pop_back();
                }
                comp.back().push_back(stk.back().v);
                comp.back().push_back(stk.back().u);
                stk.pop_back();
            }
            /*else if(par==0&&copii>1){
                comp.push_back(vector<int>());
                while(!stk.empty()&&stk.back().u!=nod&&stk.back().v!=x){
                    comp.back().push_back(stk.back().v);
                    stk.pop_back();
                }
                comp.back().push_back(stk.back().v);
                comp.back().push_back(stk.back().u);
                stk.pop_back();
            }*/
            low[nod]=min(low[nod], low[x]);
        }
        else if(x!=par)
            low[nod]=min(low[nod], tin[x]);
    }
//    if(par==0&&!stk.empty()){
//        comp.push_back(vector<int>());
//        while(stk.size()>1){
//            comp.back().push_back(stk.back().v);
//            stk.pop_back();
//        }
//        comp.back().push_back(stk.back().v);
//        comp.back().push_back(stk.back().u);
//        stk.pop_back();
//    }
}
ostream & operator <<(ostream & out, vector <int> & vec){
    for(auto &x:vec)
        out<<x<<" ";
    return out;
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++){
        in>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    dfs(1, 0);
    out<<comp.size()<<"\n";
    for(auto &x:comp)
        out<<x<<"\n";
    return 0;
}