Cod sursa(job #2555593)

Utilizator PaterucAPetruc Andrei Stefan PaterucA Data 24 februarie 2020 10:09:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream inf("biconex.in");
ofstream outf("biconex.out");

int n, m, cbx;
vector<int> v[100010], dfn, low;
vector<int> acb[100010];
stack<pair<int,int>> s;

void dfs(int ,int ,int );

int main()
{
    inf>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y;
        inf>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfn.resize(n+1);
    dfn.assign(n+1, -1);
    low.resize(n+1);
    dfs(1, 0, 0);
    outf<<cbx<<'\n';
    for(int i=1; i<=cbx; i++)
    {
        sort(begin(acb[i]), end(acb[i]));
        acb[i].erase(unique(acb[i].begin(), acb[i].end()), acb[i].end());
        for(auto it:acb[i])
            outf<<it<<' ';
        outf<<'\n';
    }
    return 0;
}

void dfs(int n, int fn, int nr)
{
    dfn[n]=low[n]=nr;
    for(auto it:v[n])
    {
        if(it==fn)
            continue;
        if(dfn[it]==-1)
        {
            s.push({n,it});
            dfs(it, n, nr+1);
            low[n]=min(low[n], low[it]);
            if(low[it]>=dfn[n])
            {
                cbx++;
                int tx, ty;
                do
                {
                    tx=s.top().first;
                    ty=s.top().second;
                    s.pop();
                    acb[cbx].push_back(tx);
                    acb[cbx].push_back(ty);
                }while(tx!=n||ty!=it);
            }
        }
        else
            low[n]=min(low[n], dfn[it]);
    }
}