Pagini recente » Cod sursa (job #1209427) | Cod sursa (job #1122613) | Cod sursa (job #785567) | Cod sursa (job #359427) | Cod sursa (job #1538390)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
vector<int> G[MAX_N];
vector<int> BC[MAX_N];
stack< pair<int,int> > ST;
int lowLink[MAX_N], dfn[MAX_N];
int N, M;
int nrBC;
void biconex(int node, int son)
{
pair<int,int> p;
nrBC++;
do
{
p = ST.top();
ST.pop();
BC[ nrBC ].emplace_back(p.first);
BC[ nrBC ].emplace_back(p.second);
} while (p.first != node || p.second != son);
}
void dfs(int node, int nr)
{
lowLink[node] = dfn[node] = nr;
for (int son : G[node])
{
if (dfn[son] == 0)
{
ST.push({node, son});
dfs(son, nr + 1);
lowLink[node] = min(lowLink[node], lowLink[son]);
if (lowLink[node] >= dfn[node])
{
biconex(node, son);
}
}
else
{
lowLink[node] = min(lowLink[node], dfn[son]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &N, &M);
while (M--)
{
int x, y;
scanf("%d%d", &x, &y);
G[x].emplace_back(y);
G[y].emplace_back(x);
}
dfs(1, 1);
printf("%d\n", nrBC);
for (int i = 1; i <= nrBC; ++i)
{
sort(BC[i].begin(), BC[i].end());
BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());
for (int x : BC[i])
printf("%d ", x);
puts("");
}
return 0;
}