Cod sursa(job #1134286)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 6 martie 2014 12:31:39
Problema Componente biconexe Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <vector>
#include <stack>
#define minim(a,b) (a<b)?(a):(b)
#define nmax 10005
using namespace std;

stack <int> stk;
vector <int> g[nmax];
vector <int> r[nmax]; int rp;
int niv[nmax];
int low[nmax];
bool viz[nmax];
int n,m,snr;

void dfs(int start,int tata) {
    viz[start] = true;
    low[start] = niv[start];
    stk.push(start);
    for (vector <int> :: iterator it = g[start].begin();it != g[start].end();it++) {
        if (viz[*it]) {
            if (*it != tata) low[start] = minim(low[start],niv[*it]);
            continue;
        }
        if (start == 1) snr++;
        niv[*it] = niv[start] +1;
        dfs(*it,start);
        low[start] = minim(low[*it],low[start]);
        if (niv[start] <= low[*it]) {
            rp++;
            while (stk.top() != start) {
                r[rp].push_back(stk.top());
                stk.pop();
            }
            r[rp].push_back(start);
        }
    }
}

int main() {
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    printf("%d\n",rp);
    for (int i=1;i<=rp;i++) {
        for (vector <int> :: iterator it = r[i].begin();it != r[i].end();it++) printf("%d ",*it);
        printf("\n");
    }
    return 0;
}