Pagini recente » Cod sursa (job #1554376) | Cod sursa (job #2953578) | Cod sursa (job #233836) | Cod sursa (job #3166183) | Cod sursa (job #2535211)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
constexpr int NMAX = 1e5 + 3;
int n, m;
vector <int> G[NMAX];
int Nivel[NMAX];
int Low[NMAX];
vector <vector <int> > sol;
deque <pair <int, int> > D;
void Drum (pair <int, int> muchie)
{
vector <int> aux;
while (!D.empty())
{
int x = D.back().first;
int y = D.back().second;
D.pop_back();
aux.push_back(x);
aux.push_back(y);
if (x == muchie.first || y == muchie.second)
break;
}
sort(aux.begin(), aux.end());
sol.push_back(aux);
}
void Dfs (int node, int dad, int level)
{
Low[node] = Nivel[node] = level;
for (auto it : G[node])
{
if (it == dad) continue;
if (Nivel[it] == -1)
{
D.push_back({node, it});
Dfs(it, node, level+1);
Low[node] = min(Low[node], Low[it]);
if (Low[it] >= Nivel[node])
Drum({node, it});
}
else Low[node] = min(Low[node], Nivel[it]);
}
}
int main()
{
f >> n >> m;
for (int i = 1; i <= n; ++i)
Nivel[i] = -1;
for (int i = 1; i <= m; ++i)
{
int x, y;
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Dfs(1, 0, 1);
g << sol.size() << '\n';
for (int i = 0; i < sol.size(); ++i)
{
g << sol[i][0] << " ";
for (int j = 1; j < sol[i].size(); ++j)
if (sol[i][j] != sol[i][j-1]) g << sol[i][j] << " ";
g << '\n';
}
return 0;
}