Cod sursa(job #1156689)

Utilizator CristinaElenaFMI Ciort Elena Cristina CristinaElena Data 27 martie 2014 21:38:34
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100005
 
using namespace std;
 
vector<int> gf[nmax], sol[nmax];
int n, m, H[nmax], nv[nmax], r;
stack<pair<int,int> > st;
int viz[nmax];
 
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){
 
    H[nod] = nv[nod] = nr;
 
    for(unsigned 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 (H[nod] > H[ gf[nod][i] ])
                H[nod] = H[ gf[nod][i] ];
            if (H[ gf[nod][i] ] >= nv[nod]){
                r++;
                int x, y;
                for(int i=1; i<=n; i++) viz[i] = 0;
                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;
                }while(x != nod || y != gf[nod][i]);
            }
        }else if (H[nod] > nv[ gf[nod][i] ])
                    H[nod] = nv[ gf[nod][i] ];
    }
 
 
}
 
void scrie(){
 
    g<<r<<"\n";
    for(int i=1; i<=r; i++){
        for(unsigned int j=0; j < sol[i].size(); j++)
            g<<sol[i][j]<<" ";
        g<<"\n";
    }
 
}
 
int main(){
 
    citeste();
    dfs(1,0,0);
    scrie();
 
    f.close();
    g.close();
 
    return 0;
 
 
}