Cod sursa(job #994777)

Utilizator assa98Andrei Stanciu assa98 Data 6 septembrie 2013 12:21:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie {
    int a,b;
    muchie() {
        a=b=0;
    }
    muchie(int x,int y) {
        a=x;
        b=y;
    }
};

const int MAX_N=100100;
const int MAX_M=100100;

vector<int> A[MAX_N];
int h[MAX_N];
int hmin[MAX_N];

muchie st[MAX_M];
int size;

vector< vector<int> > ans;

void make_bc(int x,int y) {
    vector<int> sol;
    
    int a=st[size].a,b=st[size].b;
    size--;
    sol.push_back(a);
    sol.push_back(b);
    while(size&&(a!=x||b!=y) ) {
        a=st[size].a,b=st[size].b;
        size--;
        sol.push_back(a);
        sol.push_back(b);
    }

    sort(sol.begin(),sol.end());
    vector<int>:: iterator it=unique(sol.begin(),sol.end());
    sol.erase(it,sol.end());
    ans.push_back(sol);
}

int dfs(int nod,int str,int ad) {
    h[nod]=ad;
    hmin[nod]=ad;

    for(vector<int>::iterator it=A[nod].begin();it!=A[nod].end();it++) {
        if(*it!=str) {
            if(!h[*it]) {
                st[++size]=muchie(nod,*it);
                dfs(*it,nod,ad+1);
                hmin[nod]=min(hmin[nod],hmin[*it]);
                if(hmin[*it]>=ad)
                    make_bc(nod,*it);
            }
            else {
                hmin[nod]=min(hmin[nod],h[*it]);
            }
        }
    }
}

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

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        A[a].push_back(b);
        A[b].push_back(a);
    }
    dfs(1,0,1);
    
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++,printf("\n")) {
        for(vector<int>::iterator it=ans[i].begin();it!=ans[i].end();it++) {
            printf("%d ",*it);
        }
    }

    return 0;
}