Cod sursa(job #3225632)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 18 aprilie 2024 11:28:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 kb
#ifndef LOCAL
    #pragma GCC optimize("Ofast")
#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;
bool viz[NMAX];
int h[NMAX], lo[NMAX];

vector <int> adj[NMAX];
stack <int> st;
vector <vector <int>> sol;
/*******************************/
/// FUNCTIONS

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

    int a, b;
    for (int i = 1 ; i <= M ; ++ i)
    {
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}
///-------------------------------------
inline void dfs1(int node, int par)
{
    h[node] = h[par] + 1;
    for (auto u: adj[node])
    {
        if (!h[u])
            dfs1(u, node);
    }
}
///-------------------------------------
inline void dfs2(int node, int par)
{
    lo[node] = h[node];
    for (auto u: adj[node])
    {
        if (u == par || h[u] > h[node]) continue;

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

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

        dfs2(u, node);
        lo[node] = min(lo[node], lo[u]);
    }
}
///-------------------------------------
inline void dfs_biconexe(int node, int par)
{
    st.push(node);
    for (auto u: adj[node])
    {
        if (u == par || h[u] != h[node] + 1) continue;

        dfs_biconexe(u, node);
        if (lo[u] >= h[node])
        {
            vector <int> comp;
            while (st.top() != u)
            {
                comp.push_back(st.top());
                st.pop();
            }

            comp.push_back(u);
            comp.push_back(node);
            st.pop();
            sol.push_back(comp);
        }
    }
}
///-------------------------------------
inline void Solution()
{
    dfs1(1, 0);
    dfs2(1, 0);
    dfs_biconexe(1, 0);
}
///-------------------------------------
inline void Output()
{
    cout << sol.size() << "\n";
    for (auto comp: sol)
    {
        for (auto node: comp)
            cout << node << " ";
        cout << "\n";
    }
        
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}