Cod sursa(job #2576477)

Utilizator rd211Dinucu David rd211 Data 6 martie 2020 19:44:05
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100005;
int n, m;
vector<int> graf[NMAX];
stack<pair<int, int>> stac;
int ids[NMAX];
int low[NMAX];
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> componente;
void df(int node, int father, int counter)
{
    ids[node]=low[node]=counter++;
    for(auto i:graf[node])
    {
        if(i!=father)
        {
            if(ids[i]==0)
            {
                stac.push({node,i});
                df(i,node,counter);
                low[node]=min(low[node], low[i]);
                if(low[i]>=ids[node])
                {
                    vector<int> comp;
                    while(stac.top().first!=node || stac.top().second!=i)
                    {
                        comp.push_back(stac.top().first);
                        comp.push_back(stac.top().second);
                        stac.pop();
                    }
                    comp.push_back(stac.top().first);
                    comp.push_back(stac.top().second);
                    componente.push_back(comp);
                    stac.pop();
                }
            }
            else
            {
                low[node]=min(low[node], ids[i]);
            }
        }

    }
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int a, b;
        fin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    df(1,-1,1);
    fout<<componente.size()<<'\n';
    for(auto i:componente)
    {
        set<int> st;
        for(auto j:i)
            st.insert(j);
        for(auto j:st)
            fout<<j<<" ";
        fout<<'\n';
    }

    return 0;
}