Pagini recente » Cod sursa (job #2438351) | Cod sursa (job #2911539) | Cod sursa (job #965365) | Cod sursa (job #1717483) | Cod sursa (job #1185548)
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int Nmax = 100005;
bitset<Nmax> v;
vector<int> G[Nmax];
vector<vector<int>> Bcomps;
stack<int> St;
int Lvl[Nmax], LowLvl[Nmax];
int N;
void AddBcomp(const int fnode, const int node)
{
vector<int> bcomp;
while (St.top() != node)
{
bcomp.push_back(St.top());
St.pop();
}
bcomp.push_back(node);
St.pop();
bcomp.push_back(fnode);
Bcomps.push_back(bcomp);
}
void Dfs(const int node, const int lvl)
{
Lvl[node] = lvl;
LowLvl[node] = lvl;
v[node] = 1;
St.push(node);
for (auto p: G[node])
{
if (v[p])
LowLvl[node] = min(LowLvl[node], Lvl[p]);
else
{
Dfs(p, lvl + 1);
LowLvl[node] = min(LowLvl[node], LowLvl[p]);
if (LowLvl[p] >= lvl) AddBcomp(node, p);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int M;
scanf("%d%d", &N, &M);
while (M--)
{
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= N; i++)
if (!v[i])
Dfs(i, 0);
printf("%u\n", Bcomps.size());
for (auto p: Bcomps)
{
for (auto l: p)
printf("%d ", l);
printf("\n");
}
}