Cod sursa(job #1200008)

Utilizator teoionescuIonescu Teodor teoionescu Data 21 iunie 2014 15:18:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<set>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Nmax = 100005;
vector<int> G[Nmax];
set<int> Cur;
vector< set<int> > Sol;
int N,M;
struct edge{
    int a,b;
} p;
edge S[Nmax];int K;
int L[Nmax];
int Dfs(int i,int niv){
    int depth=L[i]=niv;
    for(vector<int>::iterator it=G[i].begin();it!=G[i].end();++it){
        if(L[*it]>=0){
            int reach;
            if(!L[*it]){
                p.a=i;
                p.b=*it;
                S[++K]=p;
                reach=Dfs(*it,niv+1);
            }
            else{
                reach=L[*it];
            }
            if(reach >= niv){
                while(S[K].a!=i || S[K].b!=*it){
                    Cur.insert(S[K].a);
                    Cur.insert(S[K].b);
                    K--;
                }
                Cur.insert(S[K].a);
                Cur.insert(S[K].b);
                K--;
                Sol.push_back(Cur);
                Cur.clear();
            }
            depth=min(depth,reach);
        }
    }
    L[i]=-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<<Sol.size()<<'\n';
    for(vector< set<int> >::iterator C=Sol.begin();C!=Sol.end();++C){
        for(set<int>::iterator it=C->begin();it!=C->end();++it){
            out<<*it<<' ';
        }
        out<<'\n';
    }
    return 0;
}