Cod sursa(job #2670770)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 10 noiembrie 2020 17:37:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int NMAX = 1e5;

int N, M;
vector <int> g[NMAX + 5];

stack <int> st;
vector < vector <int> > bix;

int tmp, discovery[NMAX + 5], low[NMAX + 5];

void dfs(int node, int parent)
{
    discovery[node] = low[node] = ++tmp;
    st.push(node);

    for(auto it : g[node])
        if(it != parent)
        {
            if(discovery[it] != 0)
            {
                low[node] = min(low[node], discovery[it]);
                continue;
            }

            dfs(it, node);
            low[node] = min(low[node], low[it]);

            if(discovery[node] <= low[it])
            {
                vector <int> comp;

                int k;
                do
                {
                    k = st.top();
                    st.pop();
                    comp.push_back(k);
                }
                while(k != it);

                comp.push_back(node);

                bix.push_back(comp);
            }
        }
}

int main()
{
    cin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1; i <= N; i++)
        if(discovery[i] == 0)
            dfs(i, -1);

    cout << (int)bix.size() << '\n';

    for(auto comp : bix)
    {
        for(auto it : comp)
            cout << it << ' ';
        cout << '\n';
    }

    return 0;
}