Cod sursa(job #2820120)

Utilizator icnsrNicula Ionut icnsr Data 19 decembrie 2021 21:54:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 25.56 kb
#include <bits/stdc++.h>

template<bool>
class Graph;

template<>
class Graph<false>
{
public:
        Graph(const std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
            : nr_noduri(nr_noduri)
            , l_adiacenta(std::move(l_adiacenta))
        {
        }

        int componente_conexe() const;

        std::vector<int> distante_minime(const int start) const;

        std::vector<int> sortare_topologica() const;

        std::vector<int> grade_interne() const;

        std::vector<std::vector<int>> comp_tare_conexe() const;

        std::vector<std::vector<int>> comp_biconexe() const;

        std::vector<std::pair<int, int>> muchii_critice() const;

        static std::vector<int> ciclu_euler(const int N,
                                            const std::vector<std::pair<int, int>>& muchii);

        static int disjoint_set_find(const std::vector<int>& link, int x);

        static void disjoint_set_unite(std::vector<int>& link, std::vector<int>& size, int a,
                                       int b);

        static bool hakimi(std::vector<int>);

private:
        void DFS(std::vector<bool>& visited, int src) const;

        void DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                        const int src) const;

        void BFS(std::vector<int>& dists, int start) const;

        void ctc(const int src, int& idx, std::vector<int>& indexes,
                 std::vector<int>& low_link, std::vector<unsigned char>& on_stack,
                 std::stack<int>& stack, std::vector<std::vector<int>>& res) const;

        void DFS_biconexe(const int, const int, const int, std::vector<int>&,
                          std::vector<int>&, std::stack<std::pair<int, int>>&,
                          std::vector<std::vector<int>>&) const;

        void DFS_muchii_critice(const int, const int, const int, std::vector<int>&,
                                std::vector<int>&, std::stack<std::pair<int, int>>&,
                                std::vector<std::pair<int, int>>&) const;

private:
        std::size_t nr_noduri;
        std::vector<std::vector<int>> l_adiacenta;
};

template<>
class Graph<true>
{
public:
        Graph(const std::size_t nr_noduri,
              std::vector<std::vector<std::pair<int, int>>>&& l_adiacenta)
            : nr_noduri(nr_noduri)
            , adj(std::move(l_adiacenta))
        {
        }

        std::vector<std::array<int, 3>> cost_apm() const;

        std::vector<int> distante_minime_dijkstra(const int src) const;

        std::vector<std::vector<int>> distante_minime_floyd() const;

        std::pair<bool, std::vector<int>> distante_minime_bellmanford(const int src) const;

        int maxflow(const int src, const int dest) const;

        int cost_ciclu_hamilton_minim() const;

private:
        std::size_t nr_noduri;
        std::vector<std::vector<std::pair<int, int>>> adj;
};

int Graph<false>::componente_conexe() const
{
        std::vector<bool> visited(nr_noduri + 1, false);

        int res = 0;
        for(int node = 1; node <= (int)nr_noduri; ++node)
        {
                if(!visited[node])
                {
                        ++res;
                        DFS(visited, node);
                }
        }

        return res;
}

std::vector<int> Graph<false>::distante_minime(const int start) const
{
        std::vector<int> distante(nr_noduri + 1, -1);

        BFS(distante, start);

        return distante;
}

std::vector<int> Graph<false>::sortare_topologica() const
{
        std::vector<int> sorted;

        const auto grd_i = grade_interne();
        std::vector<unsigned char> viz(nr_noduri + 1, false);

        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                if(grd_i[node] == 0 && !viz[node])
                {
                        DFS_ordine(viz, sorted, node);
                }
        }

        std::reverse(sorted.begin(), sorted.end());

        return sorted;
}

std::vector<int> Graph<false>::grade_interne() const
{
        std::vector<int> res(nr_noduri + 1, 0);

        for(auto& l : l_adiacenta)
        {
                for(int v : l)
                {
                        ++res[v];
                }
        }

        return res;
}

void Graph<false>::DFS(std::vector<bool>& visited, int start) const
{
        visited[start] = true;

        for(int v : l_adiacenta[start])
        {
                if(!visited[v])
                {
                        DFS(visited, v);
                }
        }
}

void Graph<false>::DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                              const int src) const
{
        visited[src] = true;

        for(int v : l_adiacenta[src])
        {
                if(!visited[v])
                {
                        DFS_ordine(visited, res, v);
                }
        }

        res.push_back(src);
}

void Graph<false>::BFS(std::vector<int>& dists, int start) const
{
        std::queue<int> q;
        q.push(start);
        dists[start] = 0;

        while(!q.empty())
        {
                const auto node = q.front();
                q.pop();

                for(int v : l_adiacenta[node])
                {
                        if(dists[v] == -1)
                        {
                                q.push(v);
                                dists[v] = dists[node] + 1;
                        }
                }
        }
}

bool Graph<false>::hakimi(std::vector<int> degrees)
{
        if(degrees.empty())
        {
                return true;
        }

        while(true)
        {
                if(std::any_of(degrees.begin(), degrees.end(),
                               [](const int deg)
                               {
                                       return deg < 0;
                               }))
                {
                        return false;
                }

                std::sort(degrees.begin(), degrees.end());
                if(degrees.back() == 0)
                {
                        return true;
                }

                const int current_deg = degrees.back();
                degrees.pop_back();

                if(static_cast<std::size_t>(current_deg) > degrees.size())
                {
                        return false;
                }

                for(auto it = degrees.rbegin(); it != degrees.rbegin() + current_deg; ++it)
                {
                        --(*it);
                }
        }
}

std::vector<std::vector<int>> Graph<false>::comp_tare_conexe() const
{
        std::vector<std::vector<int>> res;

        int idx = 0;
        std::stack<int> stack;
        std::vector<int> indexes(nr_noduri + 1, -1);
        std::vector<unsigned char> on_stack(nr_noduri + 1, false);
        std::vector<int> low_link(nr_noduri + 1);

        for(int node = 1; node <= (int)nr_noduri; ++node)
        {
                if(indexes[node] == -1)
                {
                        ctc(node, idx, indexes, low_link, on_stack, stack, res);
                }
        }

        return res;
}

void Graph<false>::ctc(const int src, int& idx, std::vector<int>& indexes,
                       std::vector<int>& low_link, std::vector<unsigned char>& on_stack,
                       std::stack<int>& stack, std::vector<std::vector<int>>& res) const
{
        indexes[src] = idx;
        low_link[src] = idx;
        ++idx;

        stack.push(src);
        on_stack[src] = true;

        for(const int neigh : l_adiacenta[src])
        {
                if(indexes[neigh] == -1)
                {
                        ctc(neigh, idx, indexes, low_link, on_stack, stack, res);
                        low_link[src] = std::min(low_link[src], low_link[neigh]);
                }
                else if(on_stack[neigh])
                {
                        low_link[src] = std::min(low_link[src], indexes[neigh]);
                }
        }

        if(low_link[src] == indexes[src])
        {
                int w;
                std::vector<int> partial_res;
                do
                {
                        w = stack.top();
                        stack.pop();
                        on_stack[w] = false;
                        partial_res.push_back(w);
                } while(src != w);
                res.emplace_back(std::move(partial_res));
        }
}

std::vector<std::vector<int>> Graph<false>::comp_biconexe() const
{
        std::vector<int> depths(nr_noduri + 1, -1);
        std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
        std::stack<std::pair<int, int>> stack_muchii;

        std::vector<std::vector<int>> res;

        DFS_biconexe(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);

        for(auto& comp : res)
        {
                std::sort(comp.begin(), comp.end());
        }

        for(auto& comp : res)
        {
                comp.resize(std::unique(comp.begin(), comp.end()) - comp.begin());
        }

        return res;
}

void Graph<false>::DFS_biconexe(const int src, const int parent, const int current_depth,
                                std::vector<int>& depths,
                                std::vector<int>& lowest_reachable_depth,
                                std::stack<std::pair<int, int>>& stack_muchii,
                                std::vector<std::vector<int>>& res) const
{
        depths[src] = current_depth;
        lowest_reachable_depth[src] = current_depth;

        for(const int neigh : l_adiacenta[src])
        {
                if(depths[neigh] == -1 && neigh != parent)
                {
                        stack_muchii.push(std::make_pair(src, neigh));
                        DFS_biconexe(neigh, src, current_depth + 1, depths,
                                     lowest_reachable_depth, stack_muchii, res);

                        lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
                                                               lowest_reachable_depth[neigh]);

                        if(lowest_reachable_depth[neigh] >= depths[src])
                        {
                                std::vector<int> component;

                                int muchie_x;
                                int muchie_y;
                                do
                                {
                                        muchie_x = stack_muchii.top().first;
                                        muchie_y = stack_muchii.top().second;

                                        component.push_back(muchie_x);
                                        component.push_back(muchie_y);

                                        stack_muchii.pop();
                                } while(!(muchie_x == src && muchie_y == neigh));

                                res.emplace_back(std::move(component));
                        }
                }
                else if(neigh != parent)
                {
                        lowest_reachable_depth[src] =
                            std::min(lowest_reachable_depth[src], depths[neigh]);
                }
        }
}

std::vector<std::pair<int, int>> Graph<false>::muchii_critice() const
{
        std::vector<int> depths(nr_noduri + 1, -1);
        std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
        std::stack<std::pair<int, int>> stack_muchii;

        std::vector<std::pair<int, int>> res;

        DFS_muchii_critice(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);

        return res;
}

std::vector<int> Graph<false>::ciclu_euler(const int N,
                                           const std::vector<std::pair<int, int>>& muchii)
{
        std::vector<std::vector<int>> adj_muchii(N + 1);
        for(int i = 0; i < (int)muchii.size(); ++i)
        {
                const auto m = muchii[i];

                adj_muchii[m.first].push_back(i);
                adj_muchii[m.second].push_back(i);
        }

        for(int node = 1; node <= N; ++node)
        {
                if(adj_muchii[node].size() % 2 == 1)
                {
                        return std::vector<int>{};
                }
        }

        std::vector<int> ciclu;
        std::stack<int> s;
        std::unordered_set<int> used;

        s.push(1);
        while(!s.empty())
        {
                const int current = s.top();

                if(!adj_muchii[current].empty())
                {
                        const auto m = adj_muchii[current].back();
                        adj_muchii[current].pop_back();

                        if(used.find(m) == used.cend())
                        {
                                used.insert(m);

                                const int neigh =
                                    muchii[m].first xor muchii[m].second xor current;

                                s.push(neigh);
                        }
                }
                else
                {
                        s.pop();
                        ciclu.push_back(current);
                }
        }

        return ciclu;
}

void Graph<false>::DFS_muchii_critice(const int src, const int parent, const int current_depth,
                                      std::vector<int>& depths,
                                      std::vector<int>& lowest_reachable_depth,
                                      std::stack<std::pair<int, int>>& stack_muchii,
                                      std::vector<std::pair<int, int>>& res) const
{
        depths[src] = current_depth;
        lowest_reachable_depth[src] = current_depth;

        for(const int neigh : l_adiacenta[src])
        {
                if(depths[neigh] == -1 && neigh != parent)
                {
                        stack_muchii.push(std::make_pair(src, neigh));
                        DFS_muchii_critice(neigh, src, current_depth + 1, depths,
                                           lowest_reachable_depth, stack_muchii, res);

                        lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
                                                               lowest_reachable_depth[neigh]);

                        if(lowest_reachable_depth[neigh] > depths[src])
                        {
                                res.emplace_back(std::make_pair(neigh, src));
                        }
                }
                else if(neigh != parent)
                {
                        lowest_reachable_depth[src] =
                            std::min(lowest_reachable_depth[src], depths[neigh]);
                }
        }
}

int Graph<false>::disjoint_set_find(const std::vector<int>& link, int x)
{
        while(x != link[x])
        {
                x = link[x];
        }

        return x;
}

void Graph<false>::disjoint_set_unite(std::vector<int>& link, std::vector<int>& size, int a,
                                      int b)
{
        a = disjoint_set_find(link, a);
        b = disjoint_set_find(link, b);

        if(size[a] < size[b])
        {
                std::swap(a, b);
        }

        size[a] += size[b];
        link[b] = a;
}

std::vector<std::array<int, 3>> Graph<true>::cost_apm() const
{
        std::vector<std::array<int, 3>> edges;
        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                for(auto& e : adj[node])
                {
                        edges.push_back({(int)node, e.first, e.second});
                }
        }

        std::sort(edges.begin(), edges.end(),
                  [](const auto& e1, const auto& e2)
                  {
                          return e1[2] < e2[2];
                  });

        int n = nr_noduri;

        std::vector<int> link(n + 1);
        for(int i = 1; i <= n; ++i)
        {
                link[i] = i;
        }

        std::vector<int> size(n + 1, 1);

        const auto find_set = [&](int x)
        {
                while(x != link[x])
                {
                        x = link[x];
                }

                return x;
        };

        const auto unite = [&](int a, int b)
        {
                a = find_set(a);
                b = find_set(b);

                if(size[a] < size[b])
                {
                        std::swap(a, b);
                }

                size[a] += size[b];
                link[b] = a;
        };

        std::vector<const std::array<int, 3>*> idx;
        for(const auto& edge : edges)
        {
                if(find_set(edge[0]) != find_set(edge[1]))
                {
                        unite(find_set(edge[0]), find_set(edge[1]));
                        idx.push_back(&edge);
                }
        }

        std::vector<std::array<int, 3>> res;
        for(auto* ptr : idx)
        {
                res.push_back(*ptr);
        }

        return res;
}

std::vector<int> Graph<true>::distante_minime_dijkstra(const int src) const
{
        const int n = nr_noduri;

        std::vector<char> visited(n + 1, false);
        std::vector<int> distance(n + 1, INT_MAX);
        distance[src] = 0;

        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                            std::greater<std::pair<int, int>>>
            q;

        q.push({0, src});

        while(!q.empty())
        {
                const int a = q.top().second;
                q.pop();

                if(visited[a])
                {
                        continue;
                }

                visited[a] = true;

                for(auto& e : adj[a])
                {
                        const int b = e.first;
                        const int w = e.second;

                        if(distance[a] + w < distance[b])
                        {
                                distance[b] = distance[a] + w;
                                q.push({distance[b], b});
                        }
                }
        }

        return distance;
}

std::pair<bool, std::vector<int>> Graph<true>::distante_minime_bellmanford(const int src) const
{
        const int n = nr_noduri;

        std::vector<int> distance(n + 1, INT_MAX);
        std::vector<int> times_in_queue(n + 1, 0);

        std::queue<int> q;
        std::vector<char> in_queue(n + 1, false);
        bool has_negative_cycle = false;

        distance[src] = 0;
        q.push(src);
        in_queue[src] = true;

        while(!q.empty() && !has_negative_cycle)
        {
                const auto a = q.front();
                q.pop();

                in_queue[a] = false;

                for(auto& e : adj[a])
                {
                        const int b = e.first;
                        const int w = e.second;

                        if(distance[a] + w < distance[b])
                        {
                                distance[b] = distance[a] + w;

                                if(!in_queue[b])
                                {
                                        if(times_in_queue[b] > n)
                                        {
                                                has_negative_cycle = true;
                                        }
                                        else
                                        {
                                                q.push(b);
                                                in_queue[b] = true;
                                                ++times_in_queue[b];
                                        }
                                }
                        }
                }
        }

        return {has_negative_cycle, std::move(distance)};
}

std::vector<std::vector<int>> Graph<true>::distante_minime_floyd() const
{
        std::vector<std::vector<int>> dist(nr_noduri + 1,
                                           std::vector<int>(nr_noduri + 1, INT_MAX));

        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                for(auto& e : adj[node])
                {
                        dist[node][e.first] = e.second;
                }
        }

        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                dist[node][node] = 0;
        }

        for(std::size_t k = 1; k <= nr_noduri; ++k)
        {
                for(std::size_t i = 1; i <= nr_noduri; ++i)
                {
                        for(std::size_t j = 1; j <= nr_noduri; ++j)
                        {
                                if(dist[i][k] == INT_MAX || dist[k][j] == INT_MAX)
                                {
                                        continue;
                                }

                                if(dist[i][j] > dist[i][k] + dist[k][j])
                                {
                                        dist[i][j] = dist[i][k] + dist[k][j];
                                }
                        }
                }
        }

        return dist;
}

int Graph<true>::cost_ciclu_hamilton_minim() const
{
        const int INF = 1 << 27;
        const int N = nr_noduri;

        std::vector<std::vector<int>> dp(1 << (N), std::vector<int>(N, INF));
        std::vector<std::vector<int>> cost(N, std::vector<int>(N, INF));

        for(int node = 0; node < N; ++node)
        {
                for(auto& e : adj[node])
                {
                        cost[e.first][node] = e.second;
                }
        }

        dp[1][0] = 0;
        for(int i = 0; i < 1 << N; ++i)
        {
                for(int j = 0; j < N; ++j)
                {
                        if(!(i & (1 << j)))
                        {
                                continue;
                        }

                        for(auto& neigh : adj[j])
                        {
                                int k = neigh.first;

                                if(!(i & (1 << k)))
                                {
                                        continue;
                                }

                                dp[i][j] =
                                    std::min(dp[i][j], dp[i xor (1 << j)][k] + cost[k][j]);
                        }
                }
        }

        int res = INF;
        for(auto& e : adj[0])
        {
                int k = e.first;
                res = std::min(res, dp[(1 << N) - 1][k] + cost[k][0]);
        }

        if(res == INF)
        {
                return INT_MAX;
        }

        return res;
}

int Graph<true>::maxflow(const int src, const int dest) const
{
        const std::size_t N = nr_noduri;

        std::vector<std::vector<int>> capacity(N + 1, std::vector<int>(N + 1, 0));
        std::vector<std::vector<int>> flow(N + 1, std::vector<int>(N + 1, 0));
        for(std::size_t node = 1; node <= N; ++node)
        {
                for(const auto& e : adj[node])
                {
                        capacity[node][e.first] = std::max(capacity[node][e.first], e.second);
                }
        }

        const auto bfs_parents = [&]() -> std::vector<int>
        {
                std::vector<char> visited(N + 1, false);
                std::vector<int> parent(N + 1, -1);
                std::queue<int> q;

                q.push(src);
                visited[src] = true;

                while(!q.empty())
                {
                        const auto current = q.front();
                        q.pop();

                        for(const auto& neigh : adj[current])
                        {
                                if(visited[neigh.first] || capacity[current][neigh.first] <=
                                                               flow[current][neigh.first])
                                {
                                        continue;
                                }

                                if(neigh.first == dest)
                                {
                                        parent[dest] = current;
                                        return parent;
                                }

                                q.push(neigh.first);
                                parent[neigh.first] = current;
                                visited[neigh.first] = true;
                        }
                }

                return parent;
        };

        int max_flow = 0;
        while(true)
        {
                const auto parent = bfs_parents();

                if(parent[dest] == -1)
                {
                        break;
                }

                int path_min_cap = INT_MAX;
                for(int v = dest; v != src; v = parent[v])
                {
                        const int u = parent[v];
                        path_min_cap = std::min(path_min_cap, capacity[u][v] - flow[u][v]);
                }

                for(int v = dest; v != src; v = parent[v])
                {
                        const int u = parent[v];

                        flow[u][v] += path_min_cap;
                        flow[v][u] -= path_min_cap;
                }

                max_flow += path_min_cap;
        }

        return max_flow;
}

int main()
{
        int N;
        int M;

        scanf("%d %d", &N, &M);

        std::vector<std::vector<int>> adiacenta;
        adiacenta.resize(N + 1);
        for(int i = 0; i < M; ++i)
        {
                int x, y;
                scanf("%d %d", &x, &y);

                adiacenta[x].push_back(y);
                adiacenta[y].push_back(x);
        }

        const Graph<false> g(N, std::move(adiacenta));

        const auto componente_biconexe = g.comp_biconexe();

        printf("%ld\n", componente_biconexe.size());
        for(auto& comp : componente_biconexe)
        {
                for(int node : comp)
                {
                        printf("%d ", node);
                }
                putchar('\n');
        }
}

static const int redirect_io = []()
{
        std::freopen("biconex.in", "r", stdin);
        std::freopen("biconex.out", "w", stdout);
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        return 0;
}();