Cod sursa(job #2792466)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 1 noiembrie 2021 18:34:29
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.61 kb
#include <bits/stdc++.h>

using namespace std;

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


class graf {
private:
    int n, m;
    vector<int> h[100003];
    bitset<100003> viz;

    int k, dist[100003], nivel[100003], mic[100003];
    bool orientat = false;
    vector<int> transpus[100003];
    vector<int> ctc[100003];
    queue< pair<int, int> >q;
    stack<int> s;
    stack<int> s_biconex;
    vector<int> cbiconexe[100003];

    void dfs(int nod);

    void dfsctc(int nod);

    void bfs(int s);

    void dfs_biconex(int nod, int tata);

public:
    graf()
    {
        n = m = k = 0;
        for(int i = 1; i <= 100000; i++)
            dist[i] = -1;
    }

    void set_graf(int noduri, int muchii, bool Orientat);

    void adauga_muchie(int x, int y);

    void componente_conexe();

    void distante(int s);

    void sortare_topologica();

    void componente_tare_conexe();

    void componente_biconexe();
};

graf g;

int main()
{
    int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_biconexe();

    fin.close();
    fout.close();
    return 0;
}


void graf :: set_graf(int noduri, int muchii, bool Orientat)
{
    n = noduri;
    m = muchii;
    orientat = Orientat;
}

void graf :: adauga_muchie(int x, int y)
{
    if(orientat)
    {
        h[x].push_back(y);
        transpus[y].push_back(x); // ctc
    }
    else
    {
        h[x].push_back(y);
        h[y].push_back(x);
    }
}

void graf :: dfs(int nod)
{
    viz[nod] = 1;
    for(auto i : h[nod])
        if(!viz[i])
            dfs(i);

    // pentru sortarea topologica si ctc
    s.push(nod);
}

void graf :: dfsctc(int nod)
{
    viz[nod] = 1;
    ctc[k].push_back(nod);
    for(auto i : transpus[nod])
        if(!viz[i])
            dfsctc(i);
}

void graf :: bfs(int s)
{
    pair<int, int> nod;
    q.push({s, 0});
    viz[s] = 1;
    dist[s] = 0;

    while(!q.empty())
    {
        nod = q.front();
        dist[nod.first] = nod.second;
        q.pop();

        for(auto i : h[nod.first])
            if(!viz[i])
            {
                q.push({i, nod.second + 1});
                viz[i] = 1;
            }
    }
}

void graf :: componente_conexe()
{
    int nrc;
    nrc = 0;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            dfs(i);
            nrc++;
        }
    fout << nrc << "\n";
}

void graf :: distante(int s)
{
    bfs(s);
    for(int i = 1; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
}

void graf :: sortare_topologica()
{
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    fout << "\n";
}

void graf :: componente_tare_conexe() // kosaraju
{
    int top;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    viz.reset();
    while(!s.empty())
    {
        top = s.top();
        s.pop();
        if(!viz[top])
        {
            k++;
            dfsctc(top);
        }
    }

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : ctc[i])
            fout << j << " ";
        fout<<"\n";
    }
}

void graf :: dfs_biconex(int nod, int tata)
{
    cout << "\n am intrat\n";
    viz[nod] = 1;
    s_biconex.push(nod); ///-------------------------------- aici

    mic[nod] = nivel[nod] = nivel[tata] + 1;

    for(auto i : h[nod])
    {
        if(i != tata)
        {
            if(viz[i])
                mic[nod] = min(mic[nod], nivel[i]);
            else
            {
                dfs_biconex(i, nod);

                mic[nod] = min(mic[nod], mic[i]);

                if(nivel[nod] <= mic[i]) // o noua componenta biconexa
                {
                    k++;
                    while(s_biconex.top() != i)
                    {
                        cbiconexe[k].push_back(s_biconex.top());
                        s_biconex.pop();
                    }
                    s_biconex.pop();
                    cbiconexe[k].push_back(i);
                    cbiconexe[k].push_back(nod);
                }
            }
        }
    }
}

void graf :: componente_biconexe()
{
    nivel[0] = 0;
    dfs_biconex(1, 0);

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : cbiconexe[i])
            fout << j << " ";
        fout<<"\n";
    }
}