Cod sursa(job #1529302)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 20 noiembrie 2015 18:53:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define MAXN 100001

int N, M;
int nrcrt;
int viz[MAXN], mf[MAXN];
vector<int> d[MAXN];
int x, y;
vector<vector<int> > sol;
stack<pair<int, int> > st;

void unify (vector<int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

void addSol(pair<int, int> stop) {
    vector<int> scrt;
    while(true) {
        scrt.push_back(st.top().first);
        scrt.push_back(st.top().second);
        if(stop == st.top())
            break;
        st.pop();
    }
    st.pop();
    unify(scrt);
    sol.push_back(scrt);
}

void dfs(int u) {
    int i;
    nrcrt++;
    viz[u] = mf[u] = nrcrt;
    for(i = 0; i < d[u].size(); i++) {
        int nod;
        nod = d[u][i];
        if(viz[nod] == 0) {
            st.push(make_pair(u, nod));
            dfs(nod);
            if(mf[nod] < mf[u])
                mf[u] = mf[nod];
            if(viz[u] <= mf[nod])
                addSol(make_pair(u, nod));
        } else {
            if(viz[nod] < mf[u])
                mf[u] = viz[nod];
        }
    }
}

int main() {
    int i, j;
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for(i = 1; i <= M; i++) {
        scanf("%d %d", &x, &y);
        d[x].push_back(y);
        d[y].push_back(x);
    }
    dfs(1);
    printf("%d\n", sol.size());
    for(i = 0; i < sol.size(); i++) {
        for(j = 0; j < sol[i].size(); j++)
            printf("%d ", sol[i][j]);
        printf("\n");
    }
    return 0;
}