Cod sursa(job #2143979)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 26 februarie 2018 13:56:57
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 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, low[nmax], dfn[nmax], vf;
vector <int> v[nmax];
set <int> s[nmax];
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);
    }
    for(i=1; i<=n; i++) dfn[i]=-1;
}
void comp_biconexa(int x, int y)
{
    nrcomp++;
    while((vf>0)&&((x!=stiva[vf].x)||(y!=stiva[vf].y)))
    {
        s[nrcomp].insert(stiva[vf].x);  s[nrcomp].insert(stiva[vf].y);
        vf--;
    }
    s[nrcomp].insert(x);  s[nrcomp].insert(y);
        vf--;
}
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;
    f2<<nrcomp<<"\n";
    for(i=1; i<=nrcomp; i++)
    {
        for(auto it=s[i].begin(); it!=s[i].end(); ++it)
            f2<<(*it)<<' ';
        f2<<"\n";
    }
}
int main()
{
    citire();
    dfs(1, 0, 1);
    afisare();
    return 0;
}