Pagini recente » Cod sursa (job #2558694) | Cod sursa (job #2399257) | Cod sursa (job #1416115) | Cod sursa (job #1832961) | Cod sursa (job #2542149)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, cnt = 0, niv = 0, T[100001], Niv[100001], NivMin[100001];
vector<int> G[100001];
vector<int> Cb[100001];
stack<pair<int, int>> Stack;
bool V[100001];
void Dfs(int x)
{
V[x] = true;
++niv;
Niv[x] = NivMin[x] = niv;
for (int y : G[x])
{
if (!V[y])
{
T[y] = x;
Stack.emplace(x, y);
Dfs(y);
NivMin[x] = min(NivMin[x], NivMin[y]);
if (NivMin[y] >= Niv[x])
{
++cnt;
while (true)
{
int i = Stack.top().first, j = Stack.top().second;
Stack.pop();
Cb[cnt].push_back(i);
Cb[cnt].push_back(j);
if (i == x)
break;
}
}
}
else if (y != T[x])
NivMin[x] = min(NivMin[x], Niv[y]);
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
{
if (!V[i])
Dfs(i);
}
fout << cnt << '\n';
for (int i = 1; i <= cnt; ++i)
{
sort(Cb[i].begin(), Cb[i].end());
for (int j = 0; j < Cb[i].size(); ++j)
{
if (j == 0 || Cb[i][j - 1] != Cb[i][j])
fout << Cb[i][j] << " ";
}
fout << '\n';
}
return 0;
}