Cod sursa(job #2676622)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 24 noiembrie 2020 18:12:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

#define FINAL

#ifdef FINAL

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

#define cin in
#define cout out

#endif

const int NMAX = 100007;

vector<int> g[NMAX];

int indecs[NMAX], lowlink[NMAX];
stack<pair<int, int>> st;

vector<vector<int>> comps;

void make_comp(int root, int son)
{
    vector<int> ret;
    int f, s;
    do
    {
        f = st.top().first;
        s = st.top().second;
        st.pop();
        ret.push_back(f);
        ret.push_back(s);
    }
    while(f != root && s != son);
    comps.push_back(ret);
}

void dfs(int root, int father, int depth)
{
    indecs[root] = lowlink[root] = depth;
    for(auto vec : g[root])
    {
        if(vec == father) continue;

        if(indecs[vec] == 0)
        {
            st.push(make_pair(root, vec));
            dfs(vec, root, depth + 1);
            lowlink[root] = min(lowlink[root], lowlink[vec]);

            if(lowlink[vec] >= indecs[root])
                make_comp(root, vec);
        }
        else
        {
            lowlink[root] = min(lowlink[root], indecs[vec]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    dfs(1, -1, 1);

    for(auto &comp : comps)
    {
        sort(comp.begin(), comp.end());
        comp.erase(unique(comp.begin(), comp.end()), comp.end());
    }

    cout << comps.size() << '\n';
    for(auto comp : comps)
    {
        for(auto elem : comp)
            cout << elem << ' ';
        cout << '\n';
    }

    return 0;
}