Cod sursa(job #2423157)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 20 mai 2019 20:46:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int dfn[100005], low[100005], cnt, nr;
vector<int> Muchii[100005];
vector<int> Comp[100005];
stack<int> st;

void addCompBi(int u){
    ++nr;
    while(st.top() != u){
        Comp[nr].push_back(st.top());
        st.pop();
    }
    Comp[nr].push_back(st.top());
    st.pop();
}

void Biconex(int u, int niv)
{
    dfn[u] = low[u] = niv;
    st.push(u);
    for(int i = 0; i < Muchii[u].size(); ++i)
    {
        if(dfn[Muchii[u][i]] == -1){
            Biconex(Muchii[u][i], niv + 1);
            low[u] = min(low[u], low[Muchii[u][i]]);
            if(low[Muchii[u][i]] >= dfn[u]){
                if(st.size() > 0)
                    addCompBi(Muchii[u][i]);
                Comp[nr].push_back(u);
            }
        }
        else
            low[u] = min(low[u], dfn[Muchii[u][i]]);
    }
}

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y;

        Muchii[x].push_back(y);
        Muchii[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
        dfn[i] = low[i] = -1;

    Biconex(1, 1);

    fout << nr << '\n';
    for(int i = 1; i <= nr; ++i){
        for(auto it: Comp[i])
            fout << it << ' ';
        fout << '\n';
    }
    return 0;
}