多重辺除去
(library/graph/remove_multiedges.hpp)

• View this file on GitHub
• Last update: 2022-05-05 17:37:18+09:00
• Include: #include "library/graph/remove_multiedges.hpp"

多重辺除去

$\Theta(V+E)$ で多重辺を除去する。

Required by

• Block Cut Forest (library/graph/block_cut_forest.hpp)

Code

#ifndef SUISEN_REMOVE_MULTIPLE_EDGES
#define SUISEN_REMOVE_MULTIPLE_EDGES

#include <algorithm>
#include <vector>
#include <cstdint>

namespace suisen {

void remove_multiedges(std::vector<std::vector<int>> &g) {
    std::vector<uint8_t> exists(g.size(), 0);
    for (auto &vs : g) {
        for (int v : vs) exists[v] = true;
        vs.erase(std::remove_if(vs.begin(), vs.end(), [&](int v) { return not std::exchange(exists[v], false); }), vs.end());
    }
}

} // namespace suisen


#endif // SUISEN_REMOVE_MULTIPLE_EDGES

#line 1 "library/graph/remove_multiedges.hpp"



#include <algorithm>
#include <vector>
#include <cstdint>

namespace suisen {

void remove_multiedges(std::vector<std::vector<int>> &g) {
    std::vector<uint8_t> exists(g.size(), 0);
    for (auto &vs : g) {
        for (int v : vs) exists[v] = true;
        vs.erase(std::remove_if(vs.begin(), vs.end(), [&](int v) { return not std::exchange(exists[v], false); }), vs.end());
    }
}

} // namespace suisen

Back to top page