Cod sursa(job #1703533)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 17 mai 2016 06:08:05
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.52 kb
///  Programul determina muchiile critice. Din fiecare muchie critica se obtin doua componente conexe:
/// capetele (noduri ale) muchiei + ceea ce ramane in urma eliminarii muchiei din arbore

#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;

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

const int N = 1002;

int vecin[N][N]; /// Adiacente; to-do: lista de adiacente (problema cu marcajul back edge-urilor), merge si un vector de tati
int fol[N]; /// fol[i] = 1 daca am parcurs deja muchia 'i'
int level[N]; /// Nivelul in arbore
int dfn[N]; /// Depth First Number = nivelul minim al stramosului la care pot ajunge
int n,m,cnt;

void afis()
{
    int i,j;
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j) out<<vecin[i][j]<<" ";
        out<<"\n";
    }
    out<<"\n";
}

void dfs(int poz)
{
    int i,fiu;

    fol[poz] = 1;

    for(i=1; i<=n; ++i)
    {
        fiu = i;
        if(fol[fiu] == 0 && vecin[poz][i] == 1) /// Forward edge --> DFS
        {
            vecin[poz][i] = vecin[i][poz] = 2; /// Marchez cross edge

            level[fiu] = level[poz] + 1; /// Initializez fiul (am nevoie de tata, e mai bine sa pun instructiunile aici decat la inceputul functiei)
            dfn[fiu] = level[fiu];

            dfs(fiu);
            dfn[poz] = min(dfn[poz], dfn[fiu]); /// Preiau dfn-ul fiului (desigur, daca este mai mic)
        }
        if(fol[fiu] == 1 && vecin[poz][i] == 1) /// Back edge --> actualizez Dfn
            dfn[poz] = min(dfn[poz], level[fiu]);
    }
}

void dfs_afis(int poz) /// Pt afisarea componentelor biconexe
{
    int i;

    fol[poz] = 1;
    out<<poz<<" ";

    for(i=1; i<=n; ++i)
        if(vecin[poz][i] != 0 && fol[i] == 0)
        {
            vecin[poz][i] = vecin[i][poz] = 0;
            dfs_afis(i);
        }
}

int are_fii(int poz) /// O brutalitate. Verific daca nodul 'poz' este izolat sau nu
{
    int i;

    for(i=1; i<=n; ++i)
        if(vecin[poz][i] == 1)
            return 1;

    return 0;
}

int main()
{
    int i,j,a,b;

    in>>n>>m;
    for(i=1; i<=m; ++i)
    {
        in>>a>>b;
        vecin[a][b] = vecin[b][a] = 1;
    }

    //for(i=1; i<=n; ++i) dfn[i] = N;

    //afis();

    dfn[1] = 1; /// Initializez radacina (mult mai elegant ar fi sa leg o pseudo-radacina '0' la nodul 1, ca sa scap de initailizari)
    level[1] = 1;

    dfs(1);

    //cout<<"index:  "; for(i=1; i<=n; ++i) cout<<i<<" "; cout<<"\n";
    //cout<<"level:  "; for(i=1; i<=n; ++i) cout<<level[i]<<" "; cout<<"\n";
    //cout<<"dfn:    "; for(i=1; i<=n; ++i) cout<<dfn[i]<<" "; cout<<"\n";

    //afis();

    for(i=1; i<=n; ++i) /// Aflu numarul componentelor biconexe
        for(j=i+1; j<=n; ++j)
            if(vecin[i][j] != 0 && dfn[j] == level[j])
            {
                cout<<"Muchia ("<<i<<", "<<j<<") este critica\n";
                ++cnt;
            }

    cnt *= 2;

    out<<cnt<<"\n";

    for(i=1; i<=n; ++i) /// Elimin muchiile critice, afisez cele doua noduri
        for(j=i+1; j<=n; ++j)
            if(vecin[i][j] != 0 && dfn[j] == level[j])
            {
                vecin[i][j] = vecin[j][i] = 0;
                out<<i<<" "<<j<<"\n";
            }

    for(i=1; i<=n; ++i) fol[i] = 0; /// Reinitializez fol[] pentru o noua parcurgere

    for(i=1; i<=n; ++i) /// Afisez componentele biconexe ramase
        if(fol[i] == 0 && are_fii(i))
        {
            dfs_afis(i);
            out<<"\n";
        }

    return 0;
}