Cod sursa(job #2762191)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 5 iulie 2021 23:44:48
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define nmax 100001
#define mmax 200001
using namespace std;
string prob="biconex";
ifstream in(prob+".in");
ofstream out(prob+".out");
struct node{
    int index,lowlink;
} noduri[nmax];
int ind=1;
stack<int> s;
vector<unordered_set<int> > res;
vector<int> graf[nmax];
void dfs(int nod){
    noduri[nod].index=noduri[nod].lowlink=ind++;
    s.push(nod);
    for(auto i:graf[nod]){
        if(noduri[i].index)noduri[nod].lowlink=min(noduri[i].index,noduri[nod].lowlink);
    }
    for(auto i:graf[nod]){
        if(!noduri[i].index){
            s.push(nod);
            dfs(i);
            noduri[nod].lowlink=min(noduri[i].lowlink,noduri[nod].lowlink);
            if(noduri[i].lowlink==noduri[nod].index){
            int n;
            unordered_set<int> tmp;
            do{
                n=s.top();
                tmp.insert(n);
                s.pop();
            }while(n!=nod);
            if(tmp.size()!=1)res.push_back(tmp);
        }
        }
    }
}
int main(){
    int n,m;
    in>>n>>m;
    for(;m;m--){
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(!noduri[i].index){
            dfs(i);
        }
    }
    out<<res.size()<<'\n';
    for(auto i:res){
        for(auto j:i)out<<j<<' ';
        out<<'\n';
    }
}