Pagini recente » Cod sursa (job #2602029) | Cod sursa (job #2961351) | Cod sursa (job #597415) | Cod sursa (job #2562285) | Cod sursa (job #2416259)
#include <bits/stdc++.h>
#define maxN 100002
#define maxM 200002
using namespace std;
FILE *fin = freopen("biconexe.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
int n, m;
vector < int > V[maxN];
int N, T, top;
struct Edge
{
int u, v;
} st[maxM];
int low[maxN], disc[maxN], comp[maxN];
int nrC;
vector < int > C[maxM];
void AddEdge(int u, int v)
{
V[u].push_back(v);
V[v].push_back(u);
}
void AddEStack(int u, int v)
{
st[++ top] = Edge{u, v};
}
void Bcc(Edge e)
{
++ nrC;
while (top > 0)
{
Edge crt = st[top];
-- top;
if (comp[crt.u] != nrC)
{
comp[crt.u] = nrC;
C[nrC].push_back(crt.u);
}
if (comp[crt.v] != nrC)
{
comp[crt.v] = nrC;
C[nrC].push_back(crt.v);
}
if (crt.u == e.u && crt.v == e.v)
break;
}
}
void dfs(int u, int par)
{
disc[u] = low[u] = ++ T;
int nrC = 0;
for (int v: V[u]) if (!disc[v]) ++ nrC;
for (int v : V[u])
if (!disc[v])
{
AddEStack(u, v);
dfs(v, u);
low[u] = min(low[v], low[u]);
if (low[v] >= disc[u])
Bcc(Edge{u, v});
}
else if (v != par && low[u] > disc[v])
{
low[u] = disc[v];
AddEStack(u, v);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i)
{
int u, v;
scanf("%d%d", &u, &v);
-- u;
-- v;
AddEdge(u, v);
}
for (int i = 0; i < n; ++ i)
if (!disc[i])
dfs(i, -1);
printf("%d\n", nrC);
for (int i = 1; i <= nrC; ++ i, printf("\n"))
for (int it : C[i])
printf("%d ", it + 1);
return 0;
}