Cod sursa(job #2790681)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 29 octombrie 2021 12:38:09
Problema Componente biconexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
string prob="biconex";
ifstream in(prob+".in");
ofstream out(prob+".out");
struct edge{
    int x,y;
    edge(int _x,int _y){
        x=_x;
        y=_y;
    }
};
struct node{
    bool viz;
    int ind,lowlink;
    vector<edge*> e;
} noduri[nmax];
stack<edge*> s;
int ind=1;
vector<unordered_set<int>> res;
int p[nmax];
void dfs(int nod){
    //cout<<nod<<' ';
    noduri[nod].viz=1;
    noduri[nod].ind=noduri[nod].lowlink=ind++;
    for(auto e:noduri[nod].e){
        int urm=e->x;
        if(urm==nod)urm=e->y;
        if(!noduri[urm].viz){
            p[urm]=nod;
            s.push(e);
            dfs(urm);
            noduri[nod].lowlink=min(noduri[nod].lowlink,noduri[urm].lowlink);
            if((p[nod]!=0&&noduri[urm].lowlink>=noduri[nod].ind)||(p[nod]==0&&noduri[nod].e.size()>1)){
                unordered_set<int> tmp;
                while(s.top()!=e){
                    tmp.insert(s.top()->x);
                    tmp.insert(s.top()->y);
                    s.pop();
                }
                tmp.insert(s.top()->x);
                tmp.insert(s.top()->y);
                s.pop();
                res.push_back(tmp);
            }
        }
        else if(urm!=p[nod]){
            noduri[nod].lowlink=min(noduri[nod].lowlink,noduri[urm].ind);
        }
    }
}
int main(){
    int n,m;
    in>>n>>m;
    int x,y;
    while(m--){
        in>>x>>y;
        edge *tmp=new edge(x,y);
        noduri[x].e.push_back(tmp);
        noduri[y].e.push_back(tmp);
    }
    dfs(1);
    out<<res.size()<<'\n';
    for(auto i:res){
        for(auto j:i)out<<j<<' ';
        out<<'\n';
    }
}