Cod sursa(job #1649280)

Utilizator maribMarilena Bescuca marib Data 11 martie 2016 13:06:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <stack>
#include <set>
#include <vector>
#define DMAX 200005
#define DVFM 100005
using namespace std;

int nr_bic, n, m, a, b, index;

struct muchie {
    int c1, c2;
} temp;

stack <muchie> st;

set <int> comp_bic[DMAX];

set <int>::iterator it;

vector <int> edges[DVFM];

int idx[DVFM], lwl[DVFM], dad[DVFM];

void gasit(int a, int b){
    nr_bic++;
    temp = st.top();
    while(temp.c1 != a || temp.c2 != b){
        comp_bic[nr_bic].insert(temp.c1);
        comp_bic[nr_bic].insert(temp.c2);
        st.pop();
        temp = st.top();
    }
    comp_bic[nr_bic].insert(temp.c1);
    comp_bic[nr_bic].insert(temp.c2);
    st.pop();
}

void dfs(int vf){
    int vecin;
    idx[vf] = ++index;
    lwl[vf] = idx[vf];
    for(int i = 0; i < edges[vf].size(); ++i){
        vecin = edges[vf][i];
        if(!idx[vecin]){
            dad[vecin] = vf;
            temp.c1 = vf;
            temp.c2 = vecin;
            st.push(temp);
            dfs(vecin);
            lwl[vf] = (lwl[vf] > lwl[vecin]) ? lwl[vecin] : lwl[vf];
            if(lwl[vecin] >= idx[vf]){
                gasit(vf, vecin);
            }
        }
        if(dad[vf] != vecin){
            lwl[vf] = (lwl[vf] > idx[vecin]) ? idx[vecin] : lwl[vf];
        }
    }
}

int main()
{
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        in>>a>>b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1);
    out<<nr_bic<<"\n";
    for(int i = 1; i <= nr_bic; ++i){
        for(it = comp_bic[i].begin(); it != comp_bic[i].end(); it++){
            out<<(*it)<<" ";
        }
        out<<"\n";
    }
    in.close();
    out.close();
    return 0;
}