Pagini recente » Cod sursa (job #2371234) | Cod sursa (job #905647) | Autentificare | Borderou de evaluare (job #2022265) | Cod sursa (job #2198606)
#include <bits/stdc++.h>
#define N 100001
using namespace std;
int h[N], low[N];
vector<int> G[N];
vector<vector<int>> sol;
stack<pair<int, int>> edges;
void DFS(int s, int parent)
{
low[s] = h[s];
for (int &x : G[s])
if (!h[x])
{
h[x] = h[s] + 1;
edges.push(make_pair(s, x));
DFS(x, s);
low[s] = min(low[s], low[x]);
if (low[x] >= h[s]) // s is a cut vertex
{
pair<int, int> p;
vector<int> comp;
do
{
p = edges.top();
edges.pop();
comp.push_back(p.second);
} while (p.first != s || p.second != x);
comp.push_back(s);
sol.push_back(comp);
}
}
else if (x != parent)
low[s] = min(low[s], h[x]);
}
int main()
{
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
int n, m, x, y;
scanf("%i%i", &n, &m);
while (m--)
{
scanf("%i%i", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!h[i])
h[i] = 1, DFS(i, 0);
printf("%lu\n", sol.size());
for (auto &v : sol)
{
for (int &x : v)
printf("%i ", x);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}