Cod sursa(job #986149)

Utilizator classiusCobuz Andrei classius Data 17 august 2013 21:18:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

vector<int> v[100001];
vector<vector<int> > sl;
int dph[100001],low[100001];
stack<int> stx,sty;

void add(int xx,int yy){

    vector<int> ax; int x,y;

    do{
        x=stx.top(); stx.pop();
        y=sty.top(); sty.pop();

        ax.push_back(x);
        ax.push_back(y);

    }while(x!=xx||y!=yy);

    sl.push_back(ax);

    return;
}

void dfs(int nd,int fi,int dh){

    dph[nd]=low[nd]=dh;
    for(unsigned i=0;i<v[nd].size();i++){
        if(v[nd][i]==fi) continue;
        if(dph[v[nd][i]]==-1){
            stx.push(nd);
            sty.push(v[nd][i]);
            dfs(v[nd][i],nd,dh+1);
            low[nd]=min(low[v[nd][i]],low[nd]);
            if(low[v[nd][i]]>=dph[nd])
                add(nd,v[nd][i]);

        }else low[nd]=min(low[nd],dph[v[nd][i]]);
    }

    return;
}

int main()
{
    int n,m;

    f>>n>>m;

    for(int i=1;i<=m;i++){
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i=0;i<=n;i++)
        dph[i]=-1;

    dfs(1,0,0);

    g<<sl.size()<<'\n';

    for(unsigned i=0;i<sl.size();i++,g<<'\n'){
        sort(sl[i].begin(),sl[i].end());
        sl[i].erase(unique(sl[i].begin(),sl[i].end()),sl[i].end());
        for(unsigned j=0;j<sl[i].size();j++)
            g<<sl[i][j]<<" ";
    }

    return 0;
}