C++ Library for Competitive Programming
/*
* @title グラフ/unicyclic graph
*
* verification-helper: PROBLEM https://yukicoder.me/problems/no/1254
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/unicyclic_graph.hpp"
int main() {
int n;
std::cin >> n;
std::map<std::pair<int, int>, int> edges;
emthrm::UnicyclicGraph<bool> namori(n);
for (int i = 0; i < n; ++i) {
int a, b;
std::cin >> a >> b;
--a; --b;
edges[std::minmax(a, b)] = i;
namori.add_edge(a, b, false);
}
namori.build();
std::vector<bool> bridge(n, false);
for (const emthrm::Edge<bool>& e : namori.loop) {
bridge[edges[std::minmax(e.src, e.dst)]] = true;
}
std::vector<int> p;
for (int i = 0; i < n; ++i) {
if (bridge[i]) p.emplace_back(i);
}
const int k = p.size();
std::cout << k << '\n';
for (int i = 0; i < k; ++i) {
std::cout << p[i] + 1 << " \n"[i + 1 == k];
}
return 0;
}
#line 1 "test/graph/unicyclic_graph.test.cpp"
/*
* @title グラフ/unicyclic graph
*
* verification-helper: PROBLEM https://yukicoder.me/problems/no/1254
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/unicyclic_graph.hpp"
#include <cassert>
#include <iterator>
#include <queue>
#line 8 "include/emthrm/graph/unicyclic_graph.hpp"
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/unicyclic_graph.hpp"
namespace emthrm {
template <typename CostType>
struct UnicyclicGraph {
std::vector<bool> is_in_loop;
std::vector<int> belong, mapping;
std::vector<Edge<CostType>> loop;
std::vector<std::vector<int>> invs;
std::vector<std::vector<std::vector<Edge<CostType>>>> forest;
explicit UnicyclicGraph(const int n)
: is_in_loop(n, false), belong(n, -1), mapping(n, -1), n(n), graph(n) {}
void add_edge(const int src, const int dst, const CostType cost = 0) {
const int id = srcs.size();
srcs.emplace_back(src);
dsts.emplace_back(dst);
costs.emplace_back(cost);
graph[src].emplace_back(id);
if (dst != src) [[likely]] graph[dst].emplace_back(id);
}
void build() {
dfs(-1, 0);
std::queue<int> que;
for (const Edge<CostType>& e : loop) {
const int root = e.src, forest_id = forest.size();
belong[root] = forest_id;
mapping[root] = 0;
std::vector<int> inv{root};
std::vector<std::vector<Edge<CostType>>> tree(1);
que.emplace(root);
while (!que.empty()) {
const int ver = que.front();
que.pop();
for (const int id : graph[ver]) {
const int dst = destination(id, ver);
if (belong[dst] == -1 && !is_in_loop[dst]) {
const int idx = tree.size();
belong[dst] = forest_id;
mapping[dst] = idx;
inv.emplace_back(dst);
tree[mapping[ver]].emplace_back(mapping[ver], idx, costs[id]);
tree.emplace_back(std::vector<Edge<CostType>>{
Edge<CostType>(idx, mapping[ver], costs[id])});
que.emplace(dst);
}
}
}
if (inv.size() == 1) {
belong[root] = mapping[root] = -1;
} else {
invs.emplace_back(inv);
forest.emplace_back(tree);
}
}
}
private:
const int n;
std::vector<int> srcs, dsts;
std::vector<CostType> costs;
std::vector<std::vector<int>> graph;
int destination(const int id, const int s) const {
return (srcs[id] == s ? dsts : srcs)[id];
}
bool dfs(const int prev_id, const int ver) {
is_in_loop[ver] = true;
for (const int id : graph[ver]) {
if (id == prev_id) continue;
const int dst = destination(id, ver);
loop.emplace_back(ver, dst, costs[id]);
if (is_in_loop[dst]) {
for (int i = loop.size() - 1; i >= 0; --i) {
if (loop[i].src == dst) {
for (int j = 0; j < i; ++j) {
is_in_loop[loop[j].src] = false;
}
loop.erase(loop.begin(), std::next(loop.begin(), i));
return true;
}
}
assert(false);
}
if (dfs(id, dst)) return true;
loop.pop_back();
}
is_in_loop[ver] = false;
return false;
}
};
} // namespace emthrm
#line 15 "test/graph/unicyclic_graph.test.cpp"
int main() {
int n;
std::cin >> n;
std::map<std::pair<int, int>, int> edges;
emthrm::UnicyclicGraph<bool> namori(n);
for (int i = 0; i < n; ++i) {
int a, b;
std::cin >> a >> b;
--a; --b;
edges[std::minmax(a, b)] = i;
namori.add_edge(a, b, false);
}
namori.build();
std::vector<bool> bridge(n, false);
for (const emthrm::Edge<bool>& e : namori.loop) {
bridge[edges[std::minmax(e.src, e.dst)]] = true;
}
std::vector<int> p;
for (int i = 0; i < n; ++i) {
if (bridge[i]) p.emplace_back(i);
}
const int k = p.size();
std::cout << k << '\n';
for (int i = 0; i < k; ++i) {
std::cout << p[i] + 1 << " \n"[i + 1 == k];
}
return 0;
}