Cod sursa(job #3197065)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 25 ianuarie 2024 16:30:56
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.8 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 adancime[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 tata)
{
    viz[node] = true;
    adancime[node] = adancime[tata] + 1;

    for (auto u: adj[node])
    {
        if (u == tata || viz[u]) continue;

        dfs1(u, node);
    }
}
///-------------------------------------
inline void dfs2(int node, int tata)
{
    lo[node] = adancime[node];

    for (auto u: adj[node])
    {
        if (u == tata || adancime[u] > adancime[node]) continue;

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

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

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

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

            comp.push_back(node);
            comp.push_back(u);
            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 &v: sol)
    {
        for (auto x: v)
            cout << x << " ";
        cout << "\n";
    }
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}