Pagini recente » Cod sursa (job #373581) | Cod sursa (job #3265125) | Cod sursa (job #690121) | Cod sursa (job #2367696) | Cod sursa (job #250620)
Cod sursa(job #250620)
# include <cstdio>
# include <vector>
using namespace std;
# define FIN "biconex.in"
# define FOUT "biconex.out"
# define pb push_back
# define min(a,b) (a < b ? a : b)
# define MAXN 100005
int N, M, cb, ct;
int Dfs[MAXN];
int Low[MAXN];
vector <int> A[MAXN];
vector <int> B[MAXN];
int X[MAXN], Y[MAXN];
void Bc(int T, int nod)
{
B[++cb].pb(Y[ct]);
do
{
B[cb].pb(X[ct--]);
}
while (X[ct + 1] != T || Y[ct + 1] != nod);
}
void DF(int nod, int T, int time)
{
vector <int>::iterator it;
Low[nod] = Dfs[nod] = time;
for (it = A[nod].begin(); it != A[nod].end(); ++it)
{
if (*it == T) continue;
if (Dfs[*it] == -1)
{
X[++ct] = nod; Y[ct] = *it;
DF(*it, nod, time + 1);
if (Low[*it] >= Dfs[nod]) Bc(nod, *it);
Low[nod] = min(Low[nod],Low[*it]);
}
else Low[nod] = min(Low[nod],Dfs[*it]);
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d%d",&N,&M);
int x, y;
for (int i = 1; i <= M; ++i)
{
scanf("%d%d",&x,&y);
A[x].pb(y);
A[y].pb(x);
}
cb = 0; ct = 0;
memset(Dfs, -1, sizeof(Dfs));
DF(1, 0, 0);
printf("%d\n",cb);
vector <int>::iterator it;
for (int i = 1; i <= cb; ++i)
{
for (it = B[i].begin(); it != B[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
return 0;
}