Cod sursa(job #1675200)

Utilizator malina_floreaMalina Florea malina_florea Data 5 aprilie 2016 10:13:31
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.7 kb
#include <fstream>
#include <vector>
#define DMAX 100010
using namespace std;
FILE * fin = fopen("biconex.in", "r");
FILE * fout = fopen("biconex.out", "w");

struct muchie
{
    int t, f;
};

void citire();
void DFS(int, int);
void insereaza_stiva(int, int);
void afisare_comp(int, int);
inline int minim(int, int);
void afisare();

int n, m, start=3, nrfii;
vector <int> lista[DMAX];
vector <int> sol[DMAX];

int dfn[DMAX], low[DMAX];
int nr=1;
bool viz[DMAX];

int vf;
muchie stiva[DMAX];

int nrcomp;

int main()
{
    citire();
    DFS(start, -1);
    afisare();
    
//    int i;
//    for (i=1; i<=n; i++) fprintf(fout, "%d ", dfn[i]);
//    fprintf(fout, "\n");
//    for (i=1; i<=n; i++) fprintf(fout, "%d ", low[i]);
//    fprintf(fout, "\n");
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire()
{
    int i, a, b;
    fscanf(fin, "%d %d", &n, &m);
    for (i=0; i<m; i++)
    {
        fscanf(fin, "%d %d", &a, &b);
        lista[a].push_back(b);
        lista[b].push_back(a);
    }
    
    for (i=1; i<=n; i++) dfn[i]=low[i]=-1;
}

void DFS(int x, int tata)
{
    int i, fiu;
    
    dfn[x]=low[x]=nr;
    nr++;
    
    for (i=0; i<lista[x].size(); i++)
    {
        fiu=lista[x][i];
        
        //sa nu fie muchia spre tata SAU muchie de intoarcere
        if (fiu!=tata && dfn[x]>dfn[fiu]) //dfn[fiu] e -1
            insereaza_stiva(x, fiu);
        
        if (dfn[fiu]==-1) // daca nu a mai fost vizitat
        {
            //vedem daca e varful de start
            if (x==start) nrfii++;
            
            //calculam recursiv
            DFS(fiu, x);
            low[x]=minim(low[x], low[fiu]);
            
            //punct de articulatie
            if (dfn[x]<=low[fiu])
                afisare_comp(x, fiu);
        }
        else // daca a mai fost vizitat
        {
            if (fiu!=tata)
                low[x]=minim(low[x], dfn[fiu]);
        }
    }
}

void insereaza_stiva(int t, int f)
{
    stiva[vf].t=t;
    stiva[vf].f=f;
    vf++;
}

void afisare_comp(int t, int f)
{
    bool use[DMAX];
    muchie aux;
    int i;
    
    for (i=0; i<=n; i++) use[i]=0;
    nrcomp++;
    
    do
    {
        vf--;
        aux=stiva[vf];
        use[aux.t]=use[aux.f]=true;
        
        //fprintf( fout, "%d %d ", aux.t, aux.f);
    }
    while(aux.t!=t || aux.f!=f);
//    fprintf(fout, "\n");
    
    for (i=1; i<=n; i++)
        if (use[i])
            sol[nrcomp].push_back(i);
}

inline int minim(int a, int b)
{
    if (a<b) return a;
    return b;
}

void afisare()
{
    int i, j;
    
    fprintf(fout, "%d\n", nrcomp);
    
    for (i=1; i<=nrcomp; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fprintf(fout, "%d ", sol[i][j]);
        fprintf(fout, "\n");
    }
}