Cod sursa(job #250620)

Utilizator gh09chisinau gheorghita gh09 Data 31 ianuarie 2009 12:44:10
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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, 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;
    }