Cod sursa(job #250372)

Utilizator gh09chisinau gheorghita gh09 Data 30 ianuarie 2009 19:53:50
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
# 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, Time, cb, ct;
int Dfs[MAXN];
int Low[MAXN];
vector <int> A[MAXN];
vector <int> B[MAXN];
int X[MAXN], Y[MAXN];
void DF(int nod, int T)
{
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]) 
{
X[++ct] = nod; Y[ct] = *it;
DF(*it, nod);
Low[nod] = min(Low[nod],Low[*it]);
} 
else Low[nod] = min(Low[nod],Dfs[*it]);
}
}
void BC()
{
int i;
i = 1;
for (; i <= ct;)
{
B[++cb].pb(X[i]);  B[cb].pb(Y[i++]);
for (; Low[Y[i]] < Dfs[X[i]]; ++i)
B[cb].pb(Y[i]);
}
}
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;
DF(1, 0);
BC();
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;
}