Cod sursa(job #2144011)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 26 februarie 2018 14:14:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <vector>
#include <set>
#define nmax 100005
#define mmax 200005
using namespace std;
fstream f1("biconex.in", ios::in);
fstream f2("biconex.out", ios::out);
int n, m, nrcomp, vf, lista[mmax], cap[nmax], poz;
vector <int> v[nmax], low, dfn;
set <int> s;
struct stivaaa
{
    int x, y;
}stiva[mmax];
void citire()
{
    int i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    low.resize(n+2);
    dfn.resize(n+2);
    for(i=1; i<=n; i++) dfn[i]=-1;
}
void comp_biconexa(int x, int y)
{
    int i;
    s.clear();
    while((vf>0)&&((x!=stiva[vf].x)||(y!=stiva[vf].y)))
    {
        s.insert(stiva[vf].x);  s.insert(stiva[vf].y);
        vf--;
    }
    s.insert(x);  s.insert(y);
    vf--;

    nrcomp++;
    i= cap[nrcomp]=poz+1;
    for(auto it=s.begin(); it!=s.end(); ++it)
    {
        lista[i]=*it;
        i++;
    }
    poz=i-1;
    cap[nrcomp+1]=poz+1;
}
void dfs(int nod, int tata, int niv)
{
    int vec;
    low[nod]=dfn[nod]=niv;
    for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        if((*it)!= tata)
        {
            vec=*it;
            if(dfn[vec]!=-1) ///deja a fost vizitat, deci [nod, vec] muchie de intoarcere
               low[nod]=min(low[nod], dfn[vec]);
            else ///fiu nevizitat
            {
                vf++; stiva[vf].x=nod; stiva[vf].y=vec;///pui muchie din arbore (ai maxim 1 muchie de intoarcere pe care nu o mai pui)
                dfs(vec, nod, niv+1);
                low[nod]=min(low[nod], low[vec]);
                if(low[vec]>= dfn[nod])  comp_biconexa(nod, vec);///nod=pct art., scoti muchiile din comp. biconexa respectiva
            }
        }
}
void afisare()
{
    int i, j;
    f2<<nrcomp<<"\n";
    for(i=1; i<=nrcomp; i++)
    {
       for(j=cap[i]; j<cap[i+1]; j++)
           f2<<lista[j]<<' ';
        f2<<"\n";
    }
}
int main()
{
    citire();
    dfs(1, 0, 1);
    afisare();
    return 0;
}