Cod sursa(job #2797844)

Utilizator realmeabefirhuja petru realmeabefir Data 10 noiembrie 2021 17:34:56
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream f ("biconex.in");
ofstream g ("biconex.out");

int n,m,S,F;
vector<int> la[100005];

int lowLink[100005];
int ids[100005];
int id = 1;

stack<pair<int,int>> st;
vector<vector<int>> vcc;

void dfs_critice(int s)
{
    lowLink[s] = id;
    ids[s] = id;
    id++;

    for (auto& to: la[s])
    {
        if (ids[to] != -1)
        {
            lowLink[s] = min(lowLink[s], ids[to]);
            //cout << s << ' ' << to << ' ' << lowLink[s] << ' ' << ids[to] << '\n';
        }
        else
        {
            st.push({s,to});
            dfs_critice(to);

            lowLink[s] = min(lowLink[s], lowLink[to]);
            //cout << s << ' ' << to << ' ' << lowLink[s] << '\n';

            if (lowLink[to] >= ids[s])
            {
                vector<int> cc;
                while (st.top().first != from && st.top().second != to)
                {
                    cc.push_back(st.top().second);
                    st.pop();
                }
                cc.push_back(st.top().first);
                cc.push_back(st.top().second);
                st.pop();
                vcc.push_back(cc);
            }
        }
    }
}

int main()
{
    f >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x,y;
        f >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

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

    dfs_critice(1);

    g << vcc.size() << '\n';
    for (auto& row: vcc)
    {
        for (auto el: row)
            g << el << ' ';
        g << '\n';
    }

    return 0;
}