Pagini recente » Cod sursa (job #2229399) | Cod sursa (job #2683111) | Clasament prosoft2016-10 | Cod sursa (job #3162715) | Cod sursa (job #3285081)
#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;
}