Cod sursa(job #1607588)

Utilizator king25Ionut Vasi king25 Data 21 februarie 2016 13:54:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int low[nmax];
vector<int> dfn(nmax,-1);
vector <int> V[nmax];
vector < vector < int > > Sol;
stack < pair <int , int > > S;
vector <int> M;
int n,m;
void read(){
    f>>n>>m;
    int x,y;
    for(int i=0;i<m;++i){
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
}
void salveaza(int a,int b){
    int xi,yi;
    do{
        xi=S.top().first;
        yi=S.top().second;
        S.pop();
        M.push_back(xi);
        M.push_back(yi);
    }while(xi!=a || yi!=b );
    sort(M.begin(),M.end());
    M.erase(unique(M.begin(),M.end()),M.end());
    Sol.push_back(M);
    M.clear();
}
void biconex(int x,int xt,int num){
    dfn[x]=low[x]=num;
    for(vector<int>::iterator it=V[x].begin();it!=V[x].end();++it){
        if(xt==*it) continue;
        if(dfn[*it]==-1){
            S.push(make_pair(x,*it));
            biconex(*it,x,num+1);
            low[x]=min(low[x],low[*it]);
            if(low[*it]>=dfn[x]){
                salveaza(x,*it);
            }
        }else{
            low[x]=min(low[x],dfn[*it]);
        }
    }
}
int main()
{
    read();
    biconex(1,0,1);
    g<<Sol.size()<<"\n";
    for(int i=0;i<Sol.size();i++){
        for(int j=0;j<Sol[i].size();j++){
            g<<Sol[i][j]<<" ";
        }g<<"\n";
    }
    return 0;
}