Cod sursa(job #2680029)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 2 decembrie 2020 12:52:11
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 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;
int n, m, x, y;
vector <int> muchii[nmax+2];
bool viz[nmax+2];
int momIn[nmax+2];
int low[nmax+2];
int mom=0;
vector <vector <int> > comp;
vector <int> stk;
void dfs(int nod, int par){
    viz[nod]=true;
    low[nod]=momIn[nod]=++mom;
    stk.push_back(nod);
    for(auto &x:muchii[nod]){
        if(viz[x]==false){
            dfs(x, nod);
            low[nod]=min(low[x], low[nod]);
            if(low[x]==momIn[nod]){ ///adica ultimul accesibil e nodul actual
                comp.push_back(vector<int>());
                while(stk.back()!=nod){
                    comp.back().push_back(stk.back());
                    stk.pop_back();
                }
                comp.back().push_back(nod);
            }
        }
        else { ///deci a fost vizitat
            low[nod]=min(low[nod], momIn[x]);
        }
    }
    if(low[nod]==momIn[nod]&&par!=0){ ///adica e radacina
        comp.push_back(vector<int>());
        while(!stk.empty()){
            comp.back().push_back(stk.back());
            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);
    }
    for(int i=1; i<=n; i++){
        if(viz[i]==false)
            dfs(i, 0);
    }
    out<<comp.size()<<"\n";
    for(auto &x:comp)
        out<<x<<"\n";
    return 0;
}