Cod sursa(job #1620855)

Utilizator AndyCatrunaCatruna Andy AndyCatruna Data 29 februarie 2016 13:27:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#define dim 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,i,j,k,level[dim],sol,low[dim],viz[dim],m,a,b,x;
vector< int > v[dim],s[dim];
stack<int> st;
void dfs(int nod,int tata,int niv){
    viz[nod]=1;
    level[nod]=low[nod]=niv;
    st.push(nod);
    for(int i=0;i<v[nod].size();i++){
        int vecin = v[nod][i];
        if(nod!=tata){
            if(viz[vecin]==0){
                dfs(vecin,nod,niv+1);
                low[nod]=min(low[nod],low[vecin]);
                if(low[vecin]>=level[nod]){
                    sol++;
                    do{
                        x = st.top();
                        st.pop();
                        s[sol].push_back(x);
                    }while(x!=vecin);
                    s[sol].push_back(nod);
                }
            }
            else{
                low[nod]=min(low[nod],level[vecin]);
            }
        }
    }


}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++){
        if(viz[i]==0){
            dfs(i,0,1);
        }
    }
    fout<<sol<<"\n";
    for(i=1;i<=sol;i++){
        for(j=0;j<s[i].size();j++){
            fout<<s[i][j]<<" ";
        }
        fout<<"\n";
    }
    return 0;
}