Cod sursa(job #968107)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 1 iulie 2013 20:02:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <algorithm>
#include <vector>

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

#define pb push_back
#define mp make_pair
#define x first
#define y second
#define LE 200666

int level[LE],minh[LE],father_edge[LE],nr_sons[LE];
bool viz[LE],viz_edge[LE],vizn[LE],viz_node[LE];;
vector< pair<int,int> > H[LE];
vector<int> bcnx[LE];
int K;
pair<int,int> edge[LE];


void dfs(int nod,int lev) {
    int i,N=H[nod].size();
    viz_node[nod]=true;
    level[nod]=lev;
    minh[nod]=lev;

    for(i=0; i<N; ++i)
        if (viz_node[H[nod][i].x]==false) {
            father_edge[H[nod][i].x]=H[nod][i].y;
            dfs(H[nod][i].x,lev+1);
            minh[nod]=min(minh[nod],minh[H[nod][i].x]);
            nr_sons[nod]++;
        } else if (level[H[nod][i].x]<level[nod]-1)
            minh[nod]=min(minh[nod],level[H[nod][i].x]);

    if (minh[nod]>=level[nod]) {

        viz_edge[  father_edge[nod]  ]=true;

        if (nod!=1) {
            bcnx[++K].pb(edge[father_edge[nod]].x);
            bcnx[K].pb(edge[father_edge[nod]].y);
        }

        if (nr_sons[nod]>1)
            vizn[nod]=true;
    }
}

void dfs_2(int ind) {
    int nod1=edge[ind].x,nod2=edge[ind].y,i;
    viz_edge[ind]=true;
    bcnx[K].pb(nod1);
    bcnx[K].pb(nod2);

    if(vizn[nod1]==false) {
        int N=H[nod1].size();

        for(i=0; i<N; ++i)
            if (viz_edge[H[nod1][i].y]==false)
                dfs_2(H[nod1][i].y);
    }
    nod1=nod2;
    if(vizn[nod1]==false) {
        int N=H[nod1].size();

        for(i=0; i<N; ++i)
            if (viz_edge[H[nod1][i].y]==false)
                dfs_2(H[nod1][i].y);
    }
}

int main() {
    int n,m,xx,yy,i;

    f>>n>>m;
    for(i=1; i<=m; ++i) {
        f>>xx>>yy;
        H[xx].pb(mp(yy,i));
        H[yy].pb(mp(xx,i));
        edge[i]=mp(xx,yy);
    }

    dfs(1,1);

    for(i=1; i<=m; ++i)
        if (viz_edge[i]==false) {
            ++K;
            dfs_2(i);
        }
    g<<K<<'\n';
    for(i=1; i<=K; ++i)
        sort(bcnx[i].begin(),bcnx[i].end());

    for(i=1; i<=K; ++i) {
        int N=bcnx[i].size();

        for(int j=0; j<N; ++j)
            if (j==0||bcnx[i][j]!=bcnx[i][j-1])
                g<<bcnx[i][j]<<" ";

        g<<'\n';
    }


    f.close();
    g.close();
    return 0;
}