Cod sursa(job #250400)

Utilizator gh09chisinau gheorghita gh09 Data 30 ianuarie 2009 20:34:23
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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;
    }