Cod sursa(job #585422)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 29 aprilie 2011 12:46:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define NMAX 100006
#define minim(a,b) (a<b ? a : b)

stack<pii > st;
vector<vector<pii > > sol;
vector<int> v[NMAX];
int n,m,cnt;
int viz[NMAX];
int up[NMAX],dep[NMAX],h[NMAX];

void dfs(int nod)
{
    int i,vec,lim=v[nod].size();
    
    viz[nod]=1;
    dep[nod]=h[nod];
    for(i=0;i<lim;i++)
        if(!viz[vec=v[nod][i]])
        {
            h[vec]=h[nod]+1;
            up[vec]=nod;

            st.push(mp(nod,vec));
            dfs(vec);
            if (dep[vec] >= h[nod])
            {
                sol.pb(vector<pii>());
                while (st.top()!=mp(nod,vec))
                {
                    sol[cnt].pb(st.top());
                    st.pop();
                }
                sol[cnt].pb(st.top());
                st.pop();
                ++cnt;
            }
            
            dep[nod]=minim(dep[nod],dep[vec]);
        }
        else if (vec!=up[nod])
            dep[nod]=minim(dep[nod],h[vec]);
}

int main ()
{
    int i,j,lim,a,b;
    
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);

    memset(viz,0,sizeof(viz));
    
    printf("%d\n", cnt);
    for(i=0;i<cnt;i++)
    {
        lim=sol[i].size();
        for(j=0;j<lim;j++)
        {
            if(viz[a=sol[i][j].first]!=i+1)
            {
                printf("%d ", a);
                viz[a]=i+1;
            }
            if(viz[a=sol[i][j].second]!=i+1)
            {
                printf("%d ", a);            
                viz[a]=i+1;
            }
        }
        printf("\n");
    }
    return 0;
}