Cod sursa(job #2796078)

Utilizator wildcolaSTEFAN PLACINTESCU wildcola Data 7 noiembrie 2021 15:45:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.66 kb
#include<bits/stdc++.h>

using namespace std;

class GRAF
{
private:
    int n, m, s;
    vector<vector<int>> v;

public:
    GRAF(bool orientat);
    void bfs();
    void dfs(int poz, bool viz[]);
    void conex();
    void pcrit(int poz, int desc[], int low[], int tata[], list<pair<int,int>>& muc, vector<vector<int>>& ccon, int& nrconex);
    void bc();
};

GRAF::GRAF(bool orientat)
{
    freopen("biconex.in", "r", stdin);
    //scanf("%d %d %d", &n, &m, &s);
    //freopen("dfs.in", "r", stdin);
    scanf("%d %d", &n, &m);

    int x, y;
    v.resize(n+1);
    for(int i=0; i<m; ++i)
    {
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        if(!orientat)
            v[y].push_back(x);
    }
    fclose(stdin);
}

void GRAF::bfs()
{
    int d[n+1];
    fill_n(d, n+1, -1);
    d[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int poz = q.front();
        for(auto i : v[poz])
        {
            if(d[i] == -1)
            {
                q.push(i);
                d[i]=d[poz]+1;
            }
        }
        q.pop();
    }
    freopen("bfs.out", "w", stdout);
    for(int i=1; i<=n; ++i)
        printf("%d ", d[i]);
    fclose(stdout);
}

void GRAF::dfs(int poz, bool viz[])
{
    viz[poz] = true;
    for(auto i : v[poz])
    {
        if(!viz[i])
            dfs(i, viz);
    }
}

void GRAF::conex()
{
    bool viz[n+1] = {false};
    int nrconex = 0;

    for(int i=1; i<=n; ++i)
    {
        if(!viz[i])
        {
            dfs(i, viz);
            nrconex++;
        }
    }
    freopen("dfs.out", "w", stdout);
    printf("%d", nrconex);
    fclose(stdout);
}

void GRAF::pcrit(int poz, int desc[], int low[], int tata[], list<pair<int,int>>& muc, vector<vector<int>>& ccon, int& nrconex)
{
    static int time = 0;
    int cop = 0;
    desc[poz] = low[poz] = ++time;
    for(auto i : v[poz])
    {
        if(desc[i] == -1)
        {
            cop++;
            tata[i] = poz;
            muc.push_back(make_pair(poz,i));
            pcrit(i, desc, low, tata, muc, ccon, nrconex);

            low[poz] = min(low[poz], low[i]);
            if((tata[poz] == -1 && cop > 1) || (desc[poz] != -1 && low[i] >= desc[poz]))
            {
                while(muc.back().first != poz || muc.back().second != i)
                {
                    ccon[nrconex].push_back(muc.back().second);
                    muc.pop_back();
                }
                ccon[nrconex].push_back(muc.back().second);
                ccon[nrconex].push_back(muc.back().first);
                muc.pop_back();
                nrconex++;
            }

        }
        else if(i != tata[poz])
            low[poz] = min(low[poz], desc[i]);
    }
}

void GRAF::bc()
{
    int *desc = new int[n+1], *low = new int[n+1], *tata = new int[n+1];
    list<pair<int,int>>muc;
    vector<vector<int>> ccon(n);
    int aux;
    int nrconex = 0;
    fill_n(desc, n+1, -1);
    fill_n(low, n+1, -1);
    fill_n(tata, n+1, -1);

    for(int i=1; i<=n; ++i)
    {
        if(desc[i] == -1)
            pcrit(i, desc, low, tata, muc, ccon, nrconex);

        while(!muc.empty())
        {
            ccon[nrconex].push_back(muc.back().second);
            aux = muc.back().first;
            muc.pop_back();
        }
    }
    ccon[nrconex].push_back(aux);

    freopen("biconex.out", "w", stdout);
    printf("%d\n", nrconex);
    for(int i=0; i<nrconex; ++i)
    {
        for(auto j : ccon[i])
            printf("%d ", j);
        printf("\n");
    }
    fclose(stdout);
}

int main()
{
    GRAF g(false);
    g.bc();
    return 0;
}