Cod sursa(job #2792602)

Utilizator realmeabefirhuja petru realmeabefir Data 2 noiembrie 2021 00:15:31
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.97 kb
// ideea
// caut muchile critice cu alg de la muchii critice
// nodurile care compun muchile critice vor forma fiecare cate o com conexa
// elimin muchile critice si fac dfs pt a afla componentele conexe
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector<int> la[100005];

int lowLink[100005];
int ids[100005];
int id = 0;
// cate comp biconexe sunt
int biconexe = 0;
// componenta conexa curenta
int cc = 0;
vector<vector<int>> res;
// comp conexe ramase dupa ce am eliminat muchile critice
vector<vector<int>> cc_dupa_mc;

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};

unordered_map<pair<int,int>,int,hash_pair> mc;

void dfs_critice(int s, int p)
{
    lowLink[s] = id;
    ids[s] = id;
    id++;

    for (auto el: la[s])
    {
        if (ids[el] == -1)
            dfs_critice(el, s);
        if (el != p)
            lowLink[s] = min(lowLink[s], lowLink[el]);
    }

    if (lowLink[s] == ids[s] && p != -1)
    {
        mc[{s,p}] = 1;
        mc[{p,s}] = 1;
        biconexe ++;
        res.push_back({s, p});
        // adauga muchia de la s la p in mapu de muchi critice
        // cout << s << ' ' << p << '\n';
    }
}

void dfs(int s)
{
    // cout << s << '\n';
    cc_dupa_mc[cc].push_back(s);
    ids[s] = cc;
    for (auto el: la[s])
    {
        if (mc.find({s, el}) == mc.end() && mc.find({el, s}) == mc.end())
        {
            if (ids[el] == -1)
            {
                dfs(el);
            }
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y;
        f >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        ids[i] = -1;

    for (int i = 1; i <= n; i++)
    {
        if (ids[i] == -1)
            dfs_critice(i, -1);
    }

    for (int i = 1; i<= n;i++)
        ids[i] = -1;

    for (int i = 1; i <= n; i++)
    {
        if (ids[i] == -1)
        {
            cc_dupa_mc.push_back(vector<int>());
            dfs(i);
            cc++;
        }
    }

    for (auto& row: cc_dupa_mc)
    {
        if (row.size() > 1)
        {
            biconexe ++;
            // doar incrementez biconexe si afisez componentele la sfarsit
            // res.push_back(row);
        }
    }

    g << biconexe << '\n';
    for (auto& row: res)
    {
        if (row.size() == 1)
            continue;

        for (auto el: row)
            g << el << ' ';
        g << '\n';
    }

    for (auto& row: cc_dupa_mc)
    {
        if (row.size() > 1)
        {
            for (auto el: row)
                g << el << ' ';
            g << '\n';
        }
    }

    return 0;
}