Cod sursa(job #1218556)

Utilizator rangerChihai Mihai ranger Data 11 august 2014 18:18:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int nmax = 100010;
vector<int> g[nmax];
stack<pair<int,int> > st;
vector< vector< int > > sol;

int n,m,i,x,y,used[nmax],tin[nmax],fup[nmax],P[nmax],timer=0;

void dfs(int v, int p=-1) {
    used[v]=1;
    tin[v]=fup[v]=timer++;
    for (int i=0;i<g[v].size();i++)
    {
        int to = g[v][i];
        if (to==p) continue;
        if (used[to])
            fup[v]=min(fup[v],tin[to]);
        else {
            st.push(make_pair(v,to));
            dfs(to,v);
            fup[v]=min(fup[v],fup[to]);
            if (fup[to]>=tin[v]) {
                vector<int> aux;
                int x=st.top().first, y=st.top().second;
                while (x!=v || y!=to) {
                    st.pop();
                    aux.push_back(x);
                    aux.push_back(y);
                    x=st.top().first;
                    y=st.top().second;
                }
                st.pop();
                aux.push_back(x);
                aux.push_back(y);
                sol.push_back(aux);
            }

        }
    }
}

int main()
{
    cin>>n>>m;
    for (;m--;) {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    cout<<sol.size()<<"\n";
    for(i=0;i<sol.size();i++) {
        sort(sol[i].begin(),sol[i].end());
        cout<<sol[i][0]<<" ";
        for (int j=1;j<sol[i].size();j++) if (sol[i][j]!=sol[i][j-1])
             cout<<sol[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}