Pagini recente » Cod sursa (job #3174275) | Cod sursa (job #3279265) | Cod sursa (job #2579276) | Cod sursa (job #1402763) | Cod sursa (job #250997)
Cod sursa(job #250997)
# include <cstdio>
# include <vector>
using namespace std;
# define FIN "biconex.in"
# define FOUT "biconex.out"
# define min(a, b) (a < b ? a : b)
# define MAXN 100005
int N, M, i, cnt, comp;
int s[MAXN];
int Up[MAXN];
int Lvl[MAXN];
vector <int> E;
vector <int> G[MAXN];
vector <int> C[MAXN];
void find_Cb(int nod, int pap, int niv)
{
int x, y;
vector <int> :: iterator it;
Lvl[nod] = Up[nod] = niv;
for (it = G[nod].begin(); it < G[nod].end(); ++it)
{
if (*it == pap) continue;
if (!Lvl[*it])
{
E.push_back(nod);
E.push_back(*it);
find_Cb(*it, nod, niv + 1);
Up[nod] = min(Up[nod], Up[*it]);
if (Up[*it] >= Lvl[nod])
{
int x = 0, y;
++comp;
do
{
y = x;
x = *(E.end() - 1);
E.pop_back();
if (s[x] != comp) C[comp].push_back(x);
s[x] = comp;
}
while (x != nod || y != *it);
}
}
else Up[nod] = min(Up[nod], Lvl[*it]);
}
}
void print()
{
int i;
vector <int> :: iterator it;
printf("%d\n",comp);
for (i = 1; i <= comp; ++i)
{
for (it = C[i].begin(); it != C[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&N, &M);
for (i = 1; i <= M; ++i)
{
int x, y;
scanf("%d %d",&x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
cnt = comp = 0;
find_Cb(1, 0, 1);
print();
return 0;
}