Cod sursa(job #2632597)

Utilizator bem.andreiIceman bem.andrei Data 3 iulie 2020 22:46:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("biconex.in");
ofstream w("biconex.out");
int n, m, v[100002], h[100002], cnt;
vector <int> g[100002], ans[100002];
stack <int> st;
void dfs(int a, int b)
{
    v[a] = h[a] = v[b] + 1;
    st.push(a);
    for(auto it : g[a])
        if(it == b)
        {
            continue;
        }
        else
        {
            if(v[it])
            {
                h[a] = min(h[a], v[it]);
                continue;
            }

            dfs(it, a);
            h[a] = min(h[a], h[it]);
            if(v[a] <= h[it])
            {
                cnt++;
                int k;
                do
                {
                    k = st.top();
                    st.pop();
                    ans[cnt].push_back(k);
                }
                while(k != it);
                ans[cnt].push_back(a);
            }
        }
}
int main()
{
    r>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        r >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!v[i])
        {
            dfs(i, 0);
        }
    }
    w << cnt<<"\n";
    for(int i = 1; i <= cnt; i++)
    {
        for(auto it : ans[i]){
            w << it <<" ";
        }
        w <<"\n";
    }
    return 0;
}