Cod sursa(job #2002417)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 19 iulie 2017 20:05:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

const int N=100005;

struct Pair{
    int a,b;
};

vector <int> G[N];
vector <Pair> Sol[N];
stack <Pair> st;
int Reach[N], check[N], h[N],cnt;

void dfs(int x, int t){
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(Reach[y]==0){
            h[y]=h[x]+1;
            Reach[y]=h[y];
            st.push({x,y});
            dfs(y,x);

            if(Reach[y]>=h[x]){
                cnt++;

                int f;
                do{
                    f=st.top().a;
                    Sol[cnt].push_back(st.top());
                    st.pop();
                } while(f!=x);
            }
            Reach[x]=min(Reach[x],Reach[y]);
        }
        else{
            if(y!=t and h[y]<Reach[x]) Reach[x]=h[y];
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    int n,m,i,j,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    Reach[1]=h[1]=1;
    dfs(1,1);

    printf("%d\n",cnt);
    for(i=1;i<=cnt;i++){
        for(j=0;j<Sol[i].size();j++){
            x=Sol[i][j].a;
            y=Sol[i][j].b;
            if(check[x]==0) printf("%d ",x);
            if(check[y]==0) printf("%d ",y);
            check[x]=check[y]=1;
        }
        for(j=0;j<Sol[i].size();j++){
            x=Sol[i][j].a;
            y=Sol[i][j].b;
            check[x]=check[y]=0;
        }
        printf("\n");
    }

    /*printf("\n\n");
    for(i=1;i<=n;i++) printf("%d ",Reach[i]);*/

    return 0;
}