Cod sursa(job #633153)

Utilizator socheoSorodoc Ionut socheo Data 13 noiembrie 2011 00:21:36
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;
vector<vector<int> > rez;
stack<pair<int, int> > st;
vector<int> l[1001012];
int nrdf[101012], low[101012];
int n,m;

inline int minim(int a, int b)
{
    return a<b?a:b;
}
void scoate(int x, int y)
{   vector<int> aux;
    int aux1, aux2;
    do{
        aux1 = st.top().first;
        aux2 = st.top().second;
        st.pop();
        aux.push_back(aux1);
        aux.push_back(aux2);
    }while(aux1 != x || aux2 != y);
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(),aux.end()),aux.end());
rez.push_back(aux);

}
void df(int nr, int pred , int lev)
{
    nrdf[nr]=low[nr]=lev;
    for( vector<int>::iterator it = l[nr].begin(); it != l[nr].end(); it++)
        if(*it != pred)
        {
            if(nrdf[*it] == -1)
            {  st.push(make_pair(nr,*it));
                df(*it, nr, lev+1);
                low[nr] = minim(low[nr], low[*it]);
                if(low[*it] >= nrdf[nr])
                    scoate(nr, *it);
            }
            else low[nr] = minim(low[nr], low[*it]);
        }

}

int main()
{   freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d", &n, &m);
    int var1,var2;
    for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &var1, &var2);
            l[var1].push_back(var2);
            l[var2].push_back(var1);

        }
    for(int i=0; i<=n; i++)
        nrdf[i]=-1;
    df(1,0,0);
    printf("%d\n", (int)rez.size());
    for(int i=0; i< (int)rez.size(); i++)
       {
           for(vector<int>::iterator it = rez[i].begin(); it != rez[i].end(); it++)
                printf("%d ",*it);
           printf("\n");
       }
return 0;

}