graph/graph-utils.hpp

• View this file on GitHub
• Last update: 2022-07-12 17:31:52+03:00
• Include: #include "graph/graph-utils.hpp"

Depends on

• graph/graph-template.hpp

Required by

• graph/vertex-cover-small-ans.hpp

Code

#pragma once

#include "graph-template.hpp"

UnweightedGraph subgraph(UnweightedGraph g, vector<int> vs) {
    sort(all(vs));
    UnweightedGraph g2(sz(vs));
    for (int i = 0; i < (int) vs.size(); i++) {
        for (int j : g[vs[i]]) {
            auto it = lower_bound(all(vs), j);
            if (it != vs.end() && *it == j) {
                g2[i].push_back(lower_bound(all(vs), j) - vs.begin());
            }
        }
    }
    return g2;
}

#line 2 "graph/graph-utils.hpp"

#line 2 "graph/graph-template.hpp"

using UnweightedGraph = vector<vector<int>>;

UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) {
    UnweightedGraph g((size_t)N);
    if (M == -1)
        M = N - 1;
    for (int _ = 0; _ < M; _++) {
        int x, y;
        cin >> x >> y;
        if (is_1origin) {
            x--;
            y--;
        }
        g[(size_t) x].push_back(y);
        if (!is_directed)
            g[(size_t) y].push_back(x);
    }
    return g;
}
#line 4 "graph/graph-utils.hpp"

UnweightedGraph subgraph(UnweightedGraph g, vector<int> vs) {
    sort(all(vs));
    UnweightedGraph g2(sz(vs));
    for (int i = 0; i < (int) vs.size(); i++) {
        for (int j : g[vs[i]]) {
            auto it = lower_bound(all(vs), j);
            if (it != vs.end() && *it == j) {
                g2[i].push_back(lower_bound(all(vs), j) - vs.begin());
            }
        }
    }
    return g2;
}

Back to top page