Cod sursa(job #1149824)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 22 martie 2014 12:05:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

stack < pair<int,int> > st;
 pair<int,int>  p;
vector <int> l[100010],v[100010];
int niv[100100],low[100010],n,m,x,y,i,j,cb;

void dfs( int nod, int nivel, int pr ) {

    niv[nod]=nivel;
    low[nod]=nivel;

    for (int i=0;i<l[nod].size(); i++) {
        if (l[nod][i]!=pr) {
            if (niv[l[nod][i]]==0) {
                st.push(make_pair(nod,l[nod][i]));
                dfs(l[nod][i],nivel+1,nod);
                if (niv[nod]<=low[l[nod][i]]) {
                    cb++;
                    do {
                        p = st.top();
                        st.pop();
                        v[cb].push_back (p.first);
                        v[cb].push_back (p.second);


                    }while (p.first!=nod && p.second!=l[nod][i]);
                }
            }

            low[nod]=min(low[nod], low[l[nod][i]]);
        }
    }
}


int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (niv[i]==0)
            dfs(i,1,0);

    fout<<cb<<"\n";
    for (i=1;i<=cb;i++) {
        sort (v[i].begin(),v[i].end());
        fout<<v[i][0]<<" ";
        for (j=1;j<v[i].size();j++) {
            if (v[i][j]!=v[i][j-1])
                fout<<v[i][j]<<" ";
        }
        fout<<"\n";
    }


    return 0;
}