Graph/BuildTreePathEdge.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:24:56+09:00

Code

#pragma once
#include <vector>
#include <utility>

std::vector<int> BuildTreePathEdge(const std::vector<std::vector<std::pair<int, int>>>& graph,
                                   int s, int t) {
	int n = graph.size();
	std::vector par(n, std::pair(-1, -1));
	auto dfs = [&](auto&& f, int v, int p) -> void {
		for (auto [u, i] : graph[v]) {
			if (u != p) {
				par[u] = std::pair(v, i);
				f(f, u, v);
			}
		}
	};
	dfs(dfs, t, -1);
	std::vector<int> result;
	for (int v = s; v != t; v = par[v].first) {
		result.push_back(par[v].second);
	}
	return result;
}

#line 2 "Graph/BuildTreePathEdge.cpp"
#include <vector>
#include <utility>

std::vector<int> BuildTreePathEdge(const std::vector<std::vector<std::pair<int, int>>>& graph,
                                   int s, int t) {
	int n = graph.size();
	std::vector par(n, std::pair(-1, -1));
	auto dfs = [&](auto&& f, int v, int p) -> void {
		for (auto [u, i] : graph[v]) {
			if (u != p) {
				par[u] = std::pair(v, i);
				f(f, u, v);
			}
		}
	};
	dfs(dfs, t, -1);
	std::vector<int> result;
	for (int v = s; v != t; v = par[v].first) {
		result.push_back(par[v].second);
	}
	return result;
}

Back to top page