Pagini recente » Cod sursa (job #1918958) | Cod sursa (job #709697) | Cod sursa (job #1442618) | Cod sursa (job #2901002) | Cod sursa (job #3225632)
#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;
}