Pagini recente » Cod sursa (job #1131327) | Cod sursa (job #418125) | tema | Cod sursa (job #1383101) | Cod sursa (job #1960306)
#include <bits/stdc++.h>
#define maxN 100001
using namespace std;
FILE *fin = freopen("biconexe.in", "r", stdin);
FILE *fout = freopen("biconexe.out", "w", stdout);
/* =============== */
int n, m;
vector < int > V[maxN];
/* =============== */
int t, disc[maxN], low[maxN], parent[maxN];
int used[maxN];
struct Edge
{
int x, y;
} St[maxN];
/* =============== */
int ans, nrE;
vector < int > BCC[maxN];
void bcc(int x, int y)
{
Edge e;
++ ans;
do
{
e = St[nrE --];
if (used[e.x] != ans)
{
BCC[ans].push_back(e.x);
used[e.x] = ans;
}
if (used[e.y] != ans)
{
BCC[ans].push_back(e.y);
used[e.y] = ans;
}
if (e.x == x && e.y == y)
break;
}
while (nrE > 0);
}
void dfs(int u)
{
int nrCh = 0;
disc[u] = low[u] = ++ t;
for (int v : V[u])
if (!disc[v])
++ nrCh;
for (int v : V[u])
if (!disc[v])
{
St[++ nrE] = {u, v};
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
if ((disc[u] == 1 && nrCh > 1) ||
(disc[u] > 1 && low[v] >= disc[u])) /// check if u is an articulation point
bcc(u, v);
}
else if (v != parent[u] && low[u] > disc[v])
{
low[u] = disc[v];
St[++ nrE] = {u, v};
}
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++ i)
{
int x, y;
scanf("%d %d", &x, &y);
V[x].push_back(y);
V[y].push_back(x);
}
for (int i = 1; i <= n; ++ i)
if (!disc[i])
{
nrE = 0;
t = 0;
dfs(i);
}
printf("%d\n", ans);
for (int i = 1; i <= ans; ++ i)
{
sort(BCC[i].begin(), BCC[i].end());
int l = BCC[i].size();
for (int j = 0; j < l; ++ j)
printf("%d ", BCC[i][j]);
printf("\n");
}
return 0;
}