Cod sursa(job #671159)

Utilizator vendettaSalajan Razvan vendetta Data 30 ianuarie 2012 20:17:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define nmax 100005

using namespace std;

vector<int> gf[nmax];
int n, m, L[nmax], nv[nmax], r;
stack<pair<int,int> > st;
int viz[nmax];
set<int> sol[nmax];
int x, y;

ifstream f("biconex.in");
ofstream g("biconex.out");

void citeste(){

    f>>n>>m;
    for(int i=1; i<=m; ++i){
        int x, y;
        f>>x>>y;
        gf[x].push_back(y);
        gf[y].push_back(x);
    }
    for(int i=0; i<=n; ++i) nv[i] = -1;

}

void dfs(int nod, int T, int nr){

    L[nod] = nv[nod] = nr;

    for(int i=0; i<gf[nod].size(); ++i){
        if (gf[nod][i] == T) continue;
        if (nv[ gf[nod][i] ] == -1){
            st.push(make_pair(nod, gf[nod][i]));
            dfs(gf[nod][i], nod, nr+1);
            if (L[nod] > L[ gf[nod][i] ])
                L[nod] = L[ gf[nod][i] ];
            if (L[ gf[nod][i] ] >= nv[nod]){
                ++r;
                do{
                    x = st.top().first;
                    y = st.top().second;
                    st.pop();
                    //if(viz[y]==0) sol[r].push_back(y), viz[y]=1;
                    //if (viz[x]==0) sol[r].push_back(x), viz[x]=1;
                    sol[r].insert(x);
                    sol[r].insert(y);
                }while(x != nod || y != gf[nod][i]);
            }
        }else if (L[nod] > nv[ gf[nod][i] ])
                    L[nod] = nv[ gf[nod][i] ];
    }


}

void scrie(){

    g<<r<<"\n";
    for(int i=1; i<=r; ++i){
        for(set<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
            g<<*it<<" ";
        g<<"\n";
    }

}

int main(){

    citeste();
    dfs(1,0,0);
    scrie();

    f.close();
    g.close();

    return 0;


}