Cod sursa(job #1220824)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 18 august 2014 17:40:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <stack>
#include <list>
#include <set>
#include <bitset>
#define DIM 100011
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,low[DIM],cbc;

set<int> R[DIM];
list<int> L[DIM];
stack<pair<int,int> > S;
bitset<DIM> viz;

void dfs(int nod,int niv,int tata){
    low[nod]=niv;
    viz[nod]=1;
    list<int>::iterator it;
    pair<int,int> p;

    for(it=L[nod].begin();it!=L[nod].end();it++){
        if(*it==tata) continue;

        if(!viz[*it]){
            S.push(make_pair(nod,*it));
            dfs(*it,niv+1,nod);
            low[nod]=min(low[nod],low[*it]);

            if(low[*it]>=niv){
                //s-a generat o componenta biconexa
                cbc++;
                do{ p=S.top(),S.pop();
                    R[cbc].insert(p.first),R[cbc].insert(p.second);
                }while(p.first!=nod || p.second!=*it);
            }
        }
        else
            low[nod]=min(low[nod],low[*it]);
    }
}

int main(void){
    register int i,j,x,y;
    set<int>::iterator it;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for(i=1;i<=n;i++){
        if(!viz[i])
            dfs(i,1,0);
    }

    g<<cbc<<"\n";
    for(i=1;i<=cbc;i++){
        for(it=R[i].begin();it!=R[i].end();it++)
            g<<*it<<" ";
        g<<"\n";
    }
    return 0;
}