Cod sursa(job #2576434)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 6 martie 2020 19:25:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
const int NMAX=1e5+5;
int n,m,x,y,nr,viz[NMAX],low[NMAX],niv[NMAX];
vector <int> V[NMAX],comp[NMAX];
stack <pair<int,int>> stk;
void dfs(int x,int nod)
{
    viz[x]=1;
    low[x]=niv[x]=niv[nod]+1;
    for(auto y:V[x])
    {
        if(y==nod) continue;
        if(!viz[y])
        {
            stk.push({x,y});
            dfs(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=niv[x])
            {
                nr++;
                while(1)
                {
                    int aux=stk.top().first;
                    comp[nr].push_back(stk.top().second);
                    stk.pop();
                    if(aux==x) break;
                }
                comp[nr].push_back(x);
            }
        }
        else low[x]=min(niv[y],low[x]);
    }
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fi>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    niv[1]=low[1]=1;
    dfs(1,0);
    fo<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
        for(auto x:comp[i])
            fo<<x<<" ";
        fo<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}