So I was solving a problem using DFS and came across this abnormality.
First, I wrote this solution:
void dfs(vvi& edges, vi& in_deg, vb& visited, vi& dist, int vertex) {
visited[vertex] = true;
iter(to, edges[vertex]) {
--in_deg[to];
dist[to] = max(dist[to], dist[vertex]+1);
if (in_deg[to] == 0) {
dfs(edges, in_deg, visited, dist, to);
}
}
}
void solve(int testcase) {
int nvertices, nedges; scanf("%d %d", &nvertices, &nedges);
vvi edges(nvertices);
vi in_deg(nvertices);
fo(_, 0, nedges) {
int x, y; cin >> x >> y; --x, --y;
edges[x].PB(y);
++in_deg[y];
}
vb visited(nvertices);
vi dist(nvertices);
fo(vertex, 0, nvertices) {
if (not visited[vertex] and in_deg[vertex] == 0) {
dfs(edges, in_deg, visited, dist, vertex);
}
}
deb(dist);
printf("%d\n", *max_element(ALL(dist)));
}
This gave RE. However when I refactored this a bit:
vvi edges;
vi in_deg;
vb visited;
vi dist;
void dfs(int vertex) {
visited[vertex] = true;
iter(to, edges[vertex]) {
--in_deg[to];
dist[to] = max(dist[to], dist[vertex]+1);
if (in_deg[to] == 0) {
dfs(to);
}
}
}
void solve(int testcase) {
int nvertices, nedges; scanf("%d %d", &nvertices, &nedges);
edges.resize(nvertices);
in_deg.resize(nvertices);
visited.resize(nvertices);
dist.resize(nvertices);
fo(_, 0, nedges) {
int x, y; scanf("%d %d", &x, &y); --x, --y;
edges[x].PB(y);
++in_deg[y];
}
fo(vertex, 0, nvertices) {
if (not visited[vertex] and in_deg[vertex] == 0) {
dfs(vertex);
}
}
printf("%d\n", *max_element(ALL(dist)));
}
This one with the same logic but different declaration of the vectors passes. Any idea why?
(Excuse all the ugly marcos )