Cod sursa(job #1228725)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 15 septembrie 2014 03:02:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

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

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

    niv[nod]=low[nod]=nivel;
    pair <int,int> p;
    for (int i=0;i<l[nod].size();i++) {
        if (l[nod][i]!=pr){
            if (!niv[l[nod][i]]) {
                st.push(make_pair(nod,l[nod][i]));
                dfs(l[nod][i],nivel+1,nod);
                low[nod]=min(low[nod],low[l[nod][i]]);
                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]);
                }
            }else
                low[nod]=min(low[nod],niv[l[nod][i]]);
        }
    }
}

int main () {

    fin>>n>>m;
    while (m--) {
        fin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (!niv[i])
            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;
}