Cod sursa(job #1200005)

Utilizator teoionescuIonescu Teodor teoionescu Data 21 iunie 2014 15:15:57
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Nmax = 100001;
vector<int> G[Nmax];
vector< set<int> > Ans;
set<int> S;
int mark[Nmax],L[Nmax];
struct edge{
    int a,b; edge(){} edge(int _a,int _b){a=_a,b=_b;}
} St[2*Nmax]; int K;
int N,M;
int Dfs(int x,int niv){
    mark[x]=1;
    int depth=L[x]=niv;
    int prev=K,sonk=K;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
        int reach=0;
        if(mark[*it]==1 && L[x]-L[*it]>1){
            reach=L[*it];
        }
        else if(mark[*it]==0){
            reach=Dfs(*it,niv+1);
            St[++K]=edge(x,*it);
            sonk=K;
        }
        if(reach){
            if(reach>=L[x]){
                S.clear();
                int cur=x;
                while(St[K].a==cur){
                    S.insert(St[K].a);
                    S.insert(St[K].b);
                    cur=St[K].b;
                    K--;
                }
                /*while(K>prev){
                    S.insert(St[K].a);
                    S.insert(St[K].b);
                    K--;
                }
                sonk=K;*/
                Ans.push_back(S);
            }
            depth=min(depth,reach);
        }
        prev=sonk;
    }
    mark[x]=-1;
    return depth;
}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Dfs(1,1);
    out<<Ans.size()<<'\n';
    for(int i=0;i<Ans.size();i++){
        for(set<int>::iterator it=Ans[i].begin();it!=Ans[i].end();++it) out<<*it<<' ';
        out<<'\n';
    }
    return 0;
}