Cod sursa(job #1169882)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 12 aprilie 2014 11:55:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

stack<int> s;

vector<int> v[100005],Sol[100005];

vector<int>::iterator it;

int N,M,cb,x,y,Niv[100005],Low[100005];

inline int minim(int x, int y) {
    return x<y ? x : y;
}

void dfs(int nod, int niv) {
    Low[nod]=niv;
    Niv[nod]=niv;
    s.push(nod);
    vector<int>::iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++) {
        if(Niv[*it]==0) {
            dfs(*it,niv+1);
            Low[nod]=minim(Low[nod],Low[*it]);
            if(Niv[nod]<=Low[*it]) {
                cb++;
                while(s.top()!=*it) {
                    Sol[cb].push_back(s.top());
                    s.pop();
                }
                Sol[cb].push_back(*it);
                s.pop();
                Sol[cb].push_back(nod);
            }
        }
        else
            Low[nod]=minim(Low[nod],Niv[*it]);
    }
}

int main() {

    register int i;

    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>N>>M;
    for(i=1;i<=M;i++) {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=N;i++)
        if(Niv[i]==0)
            dfs(i,1);
    g<<cb<<"\n";
    for(i=1;i<=cb;i++) {
        for(it=Sol[i].begin();it!=Sol[i].end();it++)
            g<<*it<<" ";
        g<<"\n";
    }
    return 0;
}