Cod sursa(job #2475874)

Utilizator baltoi.teodorTeodor Baltoi baltoi.teodor Data 17 octombrie 2019 18:27:29
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define pb push_back
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> v[NMAX];
int low[NMAX];
int dfn[NMAX];
stack <pair <int, int> > S;
stack <set <int> > Sol;
set<int>set_aux;
int nrbic;
int nrord=1;
int N,M;
int dfs(int x, int tatax)
{
    dfn[x]=nrord;
    low[x]=nrord;
    nrord++;
    for(auto y:v[x])
    {
        if(y!=tatax){

            if(dfn[y]<dfn[x]) S.push({y,x});
        }
        if(dfn[y]==0) {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                nrbic++;
                set_aux.clear();
                while(S.top().first != y || S.top().second != x )
                    set_aux.insert(S.top().first), set_aux.insert(S.top().second), S.pop();
                //sol[nrbic].insert(x);
                set_aux.insert(S.top().first), set_aux.insert(S.top().second), S.pop();
                Sol.push(set_aux);
            }
        }
        else{
            if(y!=tatax) low[x]=min(low[x],dfn[y]); //muchie de intoarcere
        }
    }
}
int main()
{
    int x,y;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    S.push({0,1});
    dfs(1,0);
    fout<<nrbic<<"\n";
    while(!Sol.empty())
    {
        set_aux = Sol.top();
        Sol.pop();
        for(auto x:set_aux)
            fout<<x<<" ";
        fout<<"\n";
    }


    return 0;
}