Cod sursa(job #3285081)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 12 martie 2025 15:04:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.83 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1e5 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
int low[NMAX], tata[NMAX], h[NMAX], vis[NMAX];

vector <int> adj[NMAX]; 
vector <int> puncte_critice;
vector <pii> poduri;
vector <vector <int>> biconexe;
stack <int> dfs_stack;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N >> M;

    int x, y;
    for (int i = 0 ; i < M ; ++ i)
    {
        cin >> x >> y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}
///-------------------------------------
inline void dfs(int node, int par, int adancime)
{
    h[node] = adancime;
    tata[node] = par;
    vis[node] = true;

    for (auto u: adj[node])
    {
        if (u == par || vis[u]) continue;
        dfs(u, node, adancime + 1);
    }
}
///-------------------------------------
inline void dfs_low(int node, int par)
{
    low[node] = h[node];

    for (auto u: adj[node]) // incerc o muchie de intoarcere
    {
        if (u == par || h[u] > h[node]) continue;

        low[node] = min(low[node], h[u]);
    }

    for (auto u: adj[node]) // incerc o muchie directa catre fii
    {
        if (u == par || h[u] != h[node] + 1) continue;

        dfs_low(u, node);
        low[node] = min(low[node], low[u]);
    }
}
///-------------------------------------
inline void dfs_critice(int node, int par)
{
    bool este_critic = false;

    int nr_fii = 0;
    for (auto u: adj[node])
    {
        if (u == par) continue;
        if (h[u] != h[node] + 1) continue;

        nr_fii ++;
        if (low[u] >= h[node])
            este_critic = true;

        dfs_critice(u, node);
    }

    if (par == 0 /* suntem in radacina*/ && nr_fii >= 2) este_critic = true;

    if (este_critic) puncte_critice.push_back(node);
}
///-------------------------------------
inline void dfs_poduri(int node, int par)
{
    for (auto u: adj[node])
    {
        if (u == par || h[u] != h[node] + 1) continue;

        if (low[u] > h[node]) poduri.push_back({node, u});

        dfs_poduri(u, node);
    }
}
///-------------------------------------
inline void dfs_biconexe(int node, int par)
{
    dfs_stack.push(node);

    for (auto u: adj[node])
    {
        if (u == par || h[u] != h[node] + 1) continue;

        dfs_biconexe(u, node);

        if (low[u] >= h[node]) // am gasit o componenta biconexa
        {
            vector <int> comp;
            while (dfs_stack.top() != u)
            {
                comp.push_back(dfs_stack.top());
                dfs_stack.pop();
            }

            comp.push_back(u);
            comp.push_back(node);
            dfs_stack.pop();

            biconexe.push_back(comp);
        }
    }
}
///-------------------------------------
inline void Solution()
{
    dfs(1, 0, 1);
    dfs_low(1, 0);
    dfs_critice(1, 0);
    dfs_poduri(1, 0);
    dfs_biconexe(1, 0);

    cout << biconexe.size() << "\n";
    for (auto comp: biconexe)
    {
        for (auto node: comp) cout << node << " ";
        cout << "\n";
    }
}
///-------------------------------------
inline void Output()
{

}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}