Cod sursa(job #2475868)

Utilizator baltoi.teodorTeodor Baltoi baltoi.teodor Data 17 octombrie 2019 18:17:41
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 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;
set <int> sol[NMAX];
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++;
                while(S.top().first != y || S.top().second != x )
                    sol[nrbic].insert(S.top().first), sol[nrbic].insert(S.top().second), S.pop();
                //sol[nrbic].insert(x);
                sol[nrbic].insert(S.top().first), sol[nrbic].insert(S.top().second), S.pop();
            }
        }
        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";
    for(int i=1;i<=nrbic;++i, fout<<"\n")
        for(auto x:sol[i])
            fout<<x<<" ";
    return 0;
}