Pagini recente » Cod sursa (job #1790705) | Cod sursa (job #2140975) | Cod sursa (job #874881) | Cod sursa (job #1484370) | Cod sursa (job #3197068)
#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], adancime[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;
}