E - Count Simple Paths Editorial by en_translator
This problem asks to find “the number of paths,” which may have puzzled some of you. However, you can actually use Depth-First Search (DFS) that appeared in Problem C to solve this problem with a simple algorithm.
Specifically, implement a DFS that is expressed by the following pseudo-Python code. (Note the usage of the flag variable vis
differs from an ordinary dfs
.)
# g : The adjacecy list of graph, where the indices of vertices is subtracted by 1
vis = [False] * N
path = []
answer = 0
limit = 1000000
path = []
def dfs(c):
if answer == limit:
return
vis[c] = True
path.append(c)
answer += 1
for d in g[c]:
if vis[d] == False:
dfs(d)
vis[c] = False
path.pop()
dfs(0)
In this DFS, each state corresponds to each path. Specifically, the path represented by the sequence of vertices stored in path
in the DFS corresponds to a state of DFS.
- Here, a “state” refers to a vertex when the process of transitions of DFS is represented as a rooted tree. Also, one can show by induction that a state and a path corresponds one-to-one.
Therefore, the answer is the number of states that the DFS visits, which can be counted by actually executing the DFS. If the number of paths exceed \(10^6\), we stop the DFS and determine that the answer is \(10^6\).
What about the complexity? The function dfs
in the pseudocode is called at most \(10^6\) times, and the complexity inside dfs
is bounded by \(\mathrm{deg}(c)\), the degree of vertex \(c\). Since the degree of each vertex is at most \(10\), the number of steps is bounded by an order of \(10^6 \times 10 = 10^7\). Thus, this algorithm executes fast enough to get AC (accepted).
- Sample code (C++)
#include <iostream>
#include <vector>
using namespace std;
int calc(int N, vector<vector<int>> g) {
int ans = 0, limit = 1000000;
vector<int> vis(N);
auto dfs = [&](auto rc, int c) -> void {
if (ans == limit) return;
ans++;
vis[c] = true;
for (auto& d : g[c]) {
if (vis[d]) continue;
rc(rc, d);
}
vis[c] = false;
};
dfs(dfs, 0);
return ans;
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> g(N);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
cout << calc(N, g) << "\n";
}
posted:
last update: