Pagini recente » Cod sursa (job #2817231) | Cod sursa (job #2419296) | Cod sursa (job #2584618) | Cod sursa (job #1168406) | Cod sursa (job #282119)
Cod sursa(job #282119)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn = 100002;
int n;
vector<int> G[maxn];
vector<int> C[maxn];
int dfn[maxn], low[maxn];
bool viz[maxn];
int cached[maxn];
stack< pair<int, int> > S;
int res;
void read()
{
int m;
scanf("%d%d", &n, &m);
for (; m; --m)
{
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void solve(int x, int tx)
{
viz[x] = 1;
low[x] = dfn[x];
for (int i = 0; i < G[x].size(); ++i)
{
int next = G[x][i];
if (tx == next) continue;
if (!viz[next])
{
dfn[next] = dfn[x] + 1;
S.push(make_pair(x, next));
solve(next, x);
low[x] = min(low[x], low[next]);
if (low[next] >= dfn[x])
{
++res;
int tx, tnext;
do
{
tx = S.top().first; tnext = S.top().second;
S.pop();
if (cached[tx] != res)
{
cached[tx] = res;
C[res].push_back(tx);
}
if (cached[tnext] != res)
{
cached[tnext] = res;
C[res].push_back(tnext);
}
}
while (tx != x || tnext != next);
}
}
else low[x] = min(low[x], dfn[next]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
read();
solve(1, 0);
printf("%d\n", res);
for (int i = 1; i <= res; ++i)
{
for (int j = 0; j < C[i].size(); ++j) printf("%d ", C[i][j]);
printf("\n");
}
return 0;
}