Cod sursa(job #1167890)

Utilizator S7012MYPetru Trimbitas S7012MY Data 6 aprilie 2014 10:48:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define DN 300005
#define x first
#define y second
using namespace std;
 
typedef pair<int,int> per;
typedef vector<int>::iterator it;

int low[DN],dfn[DN],cont;
vector <vector <int> > sol;
vector<int> gr[DN];
stack <pair <int, int> > stiva;
 
void afis(int x,int y) {
    int a,b;
    vector <int> cc;
    do {
        a=stiva.top().x;
        b=stiva.top().y;
        stiva.pop();
        cc.push_back(a);
        cc.push_back(b);
    }while (a!=x || b!=y);
    sol.push_back(cc);
}
 
void biconex(int n,int fn, int nr) {
    dfn[n]=low[n]=nr;
    for(it i=gr[n].begin(); i!=gr[n].end(); ++i) {
        if(*i==fn) continue;
        if(dfn[*i]==-1) {//nu a fost viz
            stiva.push(make_pair(n,*i));
            biconex(*i,n,nr+1);
            low[n]=min(low[n],low[*i]);
            if(low[*i]>=dfn[n])
                ++cont,afis(n,*i);
        }
        else low[n] = min(low[n], dfn[*i]);
    }
}

 
int main()
{
    int i,x,y,n,m;
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    for(i=1; i<=m; i++) {
        f>>x>>y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    for(int i=0; i<=n; ++i) dfn[i]=-1;
    biconex(1,0,0);
    g<<cont<<'\n';
    for(i=0; i<sol.size(); i++) {
        sort(sol[i].begin(),sol[i].end());
        sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
        for (size_t j = 0; j < sol[i].size(); ++ j)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}