Cod sursa(job #3225545)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 17 aprilie 2024 20:53:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define vpi vector<pii>
#define vvpi vector<vpi>
#define ll long long
#define double long double
#define eb emplace_back
#define lo(x) (2 * (x) - 1)
#define up(x) (2 * (x))
//#define int long long
using namespace std;
//using namespace __gnu_pbds;

const string TASK("biconex");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout
const int N = 1e5 + 9, Inf = 0x3f3f3f3f;

int n, m;
vvi G(N);
int low[N], lvl[N], idx, comp[N], t[N];
stack<pii> stk;
//bool mat[N][N], viz[N];

vvi cbc;
vi c;

void extract_cbc(int x, int y)
{
    c.clear();
    int a, b;
    do
    {
        a = stk.top().ff, b = stk.top().ss;
        stk.pop();
//        comp[a] = comp[b] = cbc.size() + 1;
        c.pb(a), c.pb(b);
    }while(a != x && b != y);
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    cbc.pb(c);
}

void Dfs(int x, int p)
{
    low[x] = lvl[x] = ++idx;

    for(auto y : G[x])
    {
        if(y == p)continue;

        if(!lvl[y])
        {
            stk.push({x, y});
            Dfs(y, x);
            low[x] = min(low[x], low[y]);

            if(lvl[x] <= low[y])
                extract_cbc(x, y);
        }
        else low[x] = min(low[x], lvl[y]);
    }
}

//vpi ans;
//void Dfs_T(int x = 1, int p = -1)
//{
//    viz[x] = true;
//
//    if(!t[comp[x]])
//    {
//        t[comp[x]] = p;
//
//        int rep = (x == 1) ? (n + 1) : p;
//        for(auto i : cbc[comp[x] - 1])
//            if(i != rep)
//                ans.pb({i, rep});
//    }
//
//    for(auto y : G[x])
//        if(!viz[y])
//            Dfs_T(y, x);
//}
//
//void RESET()
//{
//    idx = 0;
//    cbc.clear();
//    ans.clear();
//    FOR(i, 1, n)
//    {
//        viz[i] = t[i] = low[i] = lvl[i] = comp[i] = 0;
//        G[i].clear();
//        FOR(j, 1, n)mat[i][j] = 0;
//    }
//}

void solve()
{
    cin >> n >> m;

    int x, y;
    FOR(i, 1, m)
    {
        cin >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }

    Dfs(1, 0);

    cout << cbc.size() << '\n';
    for(auto i : cbc)
    {
        for(auto j : i)cout << j << ' ';
        cout << '\n';
    }

}

signed main()
{
//    cin >> p;
    int t = 1;
//    cin >> t;
//    cout << fixed << setprecision(12);
    while(t --)
        solve();
    return 0;
}