Pagini recente » Cod sursa (job #172362) | Poze finala preONI 2006 | Cod sursa (job #1903740) | Cod sursa (job #335987) | Cod sursa (job #280084)
Cod sursa(job #280084)
#include <stdio.h>
#include <stack>
#include <bitset>
using namespace std;
#define MAX_N 100001
stack < pair <int, int> > S;
struct nod
{
int v;
nod *next;
} *L[MAX_N], *Comp[MAX_N];
int Dfn[MAX_N], Lv[MAX_N], T[MAX_N], U[MAX_N];
int N, M, R, K;
bitset <MAX_N> B;
void Add(nod *&l, int nd)
{
nod *p = new nod;
p->v = nd;
p->next = l;
l = p;
}
void Dfs(int nd)
{
Dfn[nd] = Dfn[T[nd]] + 1;
Lv[nd] = Dfn[nd];
U[nd] = 1;
nod *p;
for ( p = L[nd]; p; p = p->next )
{
if(p->v != T[nd] && Dfn[p->v] < Dfn[nd])
S.push(make_pair(nd, p->v));
if(!U[p->v])
{
T[p->v] = nd;
Dfs(p->v);
if(Lv[p->v] < Lv[nd])
Lv[nd] = Lv[p->v];
if(Lv[p->v] >= Dfn[nd])
{
pair <int, int> nv;
++ K;
while(!S.empty())
{
nv = S.top();
S.pop();
Add(Comp[K], nv.second);
if(nv.first == nd && nv.second == p->v) break;
}
Add(Comp[K], nv.first);
}
}
else if(Dfn[p->v] < Lv[nd] && T[nd] != p->v)
Lv[nd] = Dfn[p->v];
}
}
int main()
{
freopen("biconex.in", "rt", stdin);
freopen("biconex.out", "wt", stdout);
int i, x, y;
for ( scanf("%d %d", &N, &M), i = 1; i <= M; ++i )
{
scanf("%d %d", &x, &y);
Add(L[x], y);
Add(L[y], x);
}
for ( i = 1; i <= N; ++i )
if(!U[i])
{
T[i] = 0;
Dfs(i);
}
printf("%d\n", K);
for ( i = 1; i <= K; ++i )
{
B = 0;
for ( nod *p = Comp[i]; p; p = p->next )
if(!B[p->v])
{
printf("%d ", p->v);
B[p->v] = 1;
}
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}