Cod sursa(job #3142374)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 20 iulie 2023 23:27:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.7 kb
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


#define NMAX (int)(1e5 + 5)
#define MMAX (int)(2e5 + 5)

#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)

void __print(int x) { cerr << x; }

void __print(long x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned x) { cerr << x; }

void __print(unsigned long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(float x) { cerr << x; }

void __print(double x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << '\'' << x << '\''; }

void __print(const char *x) { cerr << '\"' << x << '\"'; }

void __print(const string &x) { cerr << '\"' << x << '\"'; }

void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {
    cerr << '{';
    __print(std::get<0>(x));
    cerr << ',';
    __print(std::get<1>(x));
    cerr << ',';
    __print(std::get<2>(x));
    cerr << '}';
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}

template<typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}

void _print() { cerr << "]\n"; }

template<typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}

#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif


int T, N, M;

int low[NMAX];
int h[NMAX];
// int edges[MMAX][MMAX];
bool viz[NMAX];
vector<vector<int>> bic;
vector<int> G[NMAX]; //  G[u] = i => node `u` is one endpoint of the `i`th edge; e[it].other(u) = v => (u, v) edge; the `it`th one

stack<int> st;

struct Edge {
    int u, v, c;

    int other(const int node) {  // node = u => ret. v; node = v => ret. u (return the other endpoint of the edge)
        return u ^ v ^ node;
    }
} e[MMAX];

void dfs (int u, int parent_edge_id) {
    viz[u] = true;
    for (const auto &i: G[u]) { // edge (u, v)
        int v = e[i].other(u);
        if (!viz[v]) {

            st.push(i);
            h[v] = low[v] = h[u] + 1;
            dfs(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= h[u]) {

                vector<int> comp{};
                int prev_top = -1;

                do {
                    prev_top = st.top(); st.pop();
                    int x = e[prev_top].u; int y = e[prev_top].v;
                    comp.push_back(x); comp.push_back(y);
                } while (prev_top != i);

                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                bic.push_back(comp);
            }
        }
        else { // muchie de intoarcere
            low[u] = min(low[u], h[v]);
        }

    }

}

int main() {

    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    memset(e, -1, sizeof(e));
    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        cin >> e[i].u >> e[i].v; // >> e[i].c;
        // edges[e[i].u][e[i].v] = e[i].c;

        G[e[i].u].push_back(i);
        G[e[i].v].push_back(i);
    }

    dfs(1, 0);

    cout << bic.size() << '\n';

    for (const auto &comp: bic) {
        for (const auto &x: comp) cout << x << ' ';
        cout << '\n';
    }

    return 0;
}