Cod sursa(job #1355839)

Utilizator vladutz15FMI Cornoiu Vlad vladutz15 Data 22 februarie 2015 23:32:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#define mp make_pair
#define pb push_back
#define Mn(a, b) ((a) < (b) ? (a) : (b))
#define NMAX 100003

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

int n,m,i,nrcmp,ord[NMAX],low[NMAX],nmb,x,y,nrfii,art[NMAX];
vector <int> v[NMAX],c[NMAX];
stack < pair <int, int> > st;

void ins_biconex(int x, int y)
{
    int fi,sc;
    do
    {
        fi=st.top().first;
        sc=st.top().second;
        c[nrcmp].pb(fi);
        c[nrcmp].pb(sc);
        st.pop();
    }
    while(fi!=x || sc !=y);
}

void biconex (int nod, int tata)
{
    ord[nod]=low[nod]=++nmb;
    vector <int>::iterator it;
    for (it=v[nod].begin(); it!=v[nod].end(); ++it)
    {
        if (*it==tata) continue;
        if (!ord[*it])
        {
           // if(nod==1) nrfii++;
            st.push(mp(nod,*it)); // introduc in stiva muchiile
            biconex(*it, nod);
            low[nod]=Mn(low[nod],low[*it]);
            if (low[*it]>=ord[nod]) // nod este punct de articulatie si toate muchiile intre nod si *it fac parte dintr-o componenta biconexa
            {
                if (nod!=1) art[nod]=1;
                nrcmp++;
                ins_biconex(nod, *it);
            }
        }
        else low[nod]=Mn(low[nod],ord[*it]); // (nod,*it) este muchie de intoarcere
    }
}
int main()
{
    in>>n>>m;
    for (i=1;i<=m;i++)
    {
        in>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    biconex(1,0);
    //if (nrfii>=2) art[1]=1; verific daca nodul 1 este punct de articulatie
    out<<nrcmp<<"\n";
    for (i=1;i<=nrcmp;i++)
    {
        sort(c[i].begin(), c[i].end());
        c[i].erase( unique (c[i].begin(), c[i].end()),c[i].end()); // elimin duplicitatile
        for(vector<int>::iterator it=c[i].begin();it!=c[i].end(); ++it)
            out<<*it<<" ";
        out<<"\n";
    }
}