Cod sursa(job #1563749)

Utilizator livliviLivia Magureanu livlivi Data 6 ianuarie 2016 16:43:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include<cstdio>
#include<vector>
#include<set>
#define N 100000
#define M 200000
using namespace std;

bool viz[N+1];
int lst[N+1];
int urm[2*M+1];
int vecin[2*M+1];

vector<set<int> > comp;
set<int> aux;

int xstk[M+1];
int ystk[M+1];
int k;

int nivel[N+1];

int dfs(int nod){
    int p,up,x;
    viz[nod]=true;

    up=nivel[nod];

    p=lst[nod];
    while(p!=0){
        if (viz[vecin[p]]==false){
            nivel[vecin[p]]=nivel[nod]+1;
            k++;
            xstk[k]=nod;
            ystk[k]=vecin[p];
            x=dfs(vecin[p]);

            if (x>=nivel[nod]){
                comp.push_back(aux);
                comp[comp.size()-1].insert(xstk[k]);
                comp[comp.size()-1].insert(ystk[k]);
                while(k>1 &&(xstk[k]!=nod ||ystk[k]!=vecin[p])){
                    k--;
                    comp[comp.size()-1].insert(xstk[k]);
                    comp[comp.size()-1].insert(ystk[k]);
                }
                k--;
            }
            else
            if (up>x) up=x;
        }
        else
        if (nivel[vecin[p]]<up) up=nivel[vecin[p]];
        p=urm[p];
    }

    return up;
}


void adauga(int x,int y,int i){
    vecin[i*2-1]=y;
    urm[i*2-1]=lst[x];
    lst[x]=i*2-1;

    vecin[i*2]=x;
    urm[i*2]=lst[y];
    lst[y]=i*2;
}


int main(){
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    int n,m,i,x,y;

    scanf ("%d%d",&n,&m);

    for(i=1;i<=m;i++){
        scanf ("%d%d",&x,&y);
        adauga(x,y,i);
    }

    dfs(1);

    printf ("%d\n",comp.size());
    set<int>::iterator it;
    for(i=0;i<comp.size();i++){
        for(it=comp[i].begin();it!=comp[i].end();it++)
            printf ("%d ",*it);
        printf ("\n");
    }

    return 0;
}