Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

G - Typical Path Problem

Problem Statement

Given a simple undirected graph $G$ with $N$ vertices and $M$ edges, and three integers $A$, $B$, $C$.

Does there exist a simple path from vertex $A$ to $C$ that passes through $B$?

Constraints:

$3\le N\le 2\times 10^5$
$N-1\le M\le \min(\frac{N(N-1)}2,2\times 10^5)$
$1\le A,B,C\le N$ ($A$, $B$, $C$ are distinct)

What is a simple path?
A simple path does not visit the same vertex more than once. For example, $1\to 2\to 3$ is a simple path, but $1\to 2\to 1$ is not.

Solution 1: Maximum Flow

We observe that a simple path $A\to B\to C$ exists if and only if there are two paths $B\to A$ and $B\to C$ that share no vertices except $B$. This can be modeled as a maximum flow problem.

Construct a directed graph $G'$ with $(2N+2)$ vertices:

Source: $s$
Sink: $t$
Entry points for each vertex in $G$: $x_1,\dots,x_N$
Exit points for each vertex in $G$: $y_1,\dots,y_N$

Edges are added as follows:

For each $1\le i\le N$, connect entry $x_i$ to exit $y_i$ with capacity $1$;
Connect source $s$ to $x_B$ (entry of $B$) with capacity $2$;
Connect exits $y_A$ and $y_C$ to sink $t$ with capacity $1$ each;
For each original edge $(u,v)\in E_G$, connect $y_u \to x_v$ and $y_v \to x_u$ with capacity $1$.

Compute the maximum flow from $s$ to $t$. If the flow equals $2$, the required paths exist.

Proof
A flow of $2$ must utilize both $y_A\to t$ and $y_C\to t$ edges, implying existence of $B\to A$ and $B\to C$ paths. If these paths share any vertex $v$, both flows would require passing through the $x_v\to y_v$ edge (capacity $1$), making total flow $1$. Hence, a flow of $2$ guarantees vertex-disjoint paths.

Using Dinic’s algorithm, the time complexity is $\mathcal O(N+M)$ since the maximum flow is $2$.

Code Implementation

Notations:

Source: $s=0$
Sink: $t=2n+1$
Entry of $i$: $x_i=i$
Exit of $i$: $y_i=n+i$

AC Library Implementation

AtCoder Library provides a Dinic-based max flow implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <cstdio>
#include <atcoder/maxflow>
using namespace std;

int main()
{
    int n, m, a, b, c;
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    int s = 0, t = (n << 1) + 1;
    atcoder::mf_graph<int> G(t + 1);
    G.add_edge(s, b + n, 2);
    G.add_edge(a + n, t, 1);
    G.add_edge(c + n, t, 1);
    for(int i=1; i<=n; i++)
        G.add_edge(i, i + n, 1);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G.add_edge(x + n, y, 1);
        G.add_edge(y + n, x, 1);
    }
    puts(G.flow(s, t, 2) == 2? "Yes": "No");
    return 0;
}

Manual Dinic Implementation

Dinic’s algorithm achieves $\mathcal O(N+M)$ complexity for this graph. For algorithm details, refer to OI Wiki.

Note on Memory Allocation
The transformed graph $G'$ contains $(N+2M+3)$ edges. Using static adjacency lists, allocate arrays of size $2(N+2M+3)$, which can safely be set to $1.25\times 10^6$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 400005
#define maxm 1250005
using namespace std;

int n, s, t, head[maxn], cur[maxn], dis[maxn],
    cnt, w[maxm], to[maxm], nxt[maxm];

inline void add(int u, int v, int flow)
{
    nxt[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    w[cnt++] = flow;
}

inline void add_flow(int u, int v, int f)
{
    add(u, v, f);
    add(v, u, 0);
}

inline bool bfs()
{
    memset(dis, -1, sizeof(int) * n);
    dis[s] = 0, cur[s] = head[s];
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        for(int i=head[v]; ~i; i=nxt[i])
            if(w[i])
            {
                int u = to[i];
                if(dis[u] == -1)
                {
                    dis[u] = dis[v] + 1, cur[u] = head[u];
                    if(u == t) return true;
                    q.push(u);
                }
            }
    }
    return false;
}

int dfs(int v, int flow)
{
    if(v == t) return flow;
    int res = 0;
    for(int i=cur[v]; ~i && flow; i=nxt[i])
    {
        cur[v] = i;
        int u = to[i];
        if(w[i] && dis[u] == dis[v] + 1)
        {
            int k = dfs(u, min(flow, w[i]));
            w[i] -= k;
            w[i ^ 1] += k;
            flow -= k;
            res += k;
        }
    }
    return res;
}

int main()
{
    int n, m, a, b, c;
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    s = 0, t = (n << 1) + 1, ::n = t + 1;
    memset(head, -1, sizeof(int) * ::n);
    add_flow(s, b + n, 2);
    add_flow(a + n, t, 1);
    add_flow(c + n, t, 1);
    for(int i=1; i<=n; i++)
        add_flow(i, i + n, 1);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add_flow(x + n, y, 1);
        add_flow(y + n, x, 1);
    }
    int mf = 0;
    while(bfs()) mf += dfs(s, 2);
    puts(mf == 2? "Yes": "No");
    return 0;
}

Solution 2: Block Forest (Round-square Tree)

Correctness relies on:

For any simple path $A\to C$, if $B$ lies in any biconnected component along this path, then $A\to B\to C$ exists. Otherwise, no such path exists.

Construct the block forest (round-square tree) using Tarjan’s algorithm:

Build the block forest $T$ of $G$.
Find the unique simple path $A\to C$ in $T$.
Check if $B$ is adjacent to any square node (biconnected component) on this path.

Time complexity: $\mathcal O(N+M)$, with better practical performance than flow-based solutions.

Code Implementation

Tip: Allocate double-sized arrays for block forest nodes to avoid RE.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 200005
using namespace std;

inline void setmin(int& x, int y)
{
    if(y < x) x = y;
}

vector<int> G[maxn], T[maxn << 1];

inline void add_edge(vector<int>* G, int x, int y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}

int dfc, dfn[maxn], low[maxn], top, st[maxn], cnt;

void tarjan(int v)
{
    low[v] = dfn[v] = ++dfc;
    st[++top] = v;
    for(int u: G[v])
        if(!dfn[u])
        {
            tarjan(u);
            setmin(low[v], low[u]);
            if(low[u] == dfn[v])
            {
                add_edge(T, v, ++cnt);
                do add_edge(T, st[top], cnt);
                while(st[top--] != u);
            }
        }
        else setmin(low[v], dfn[u]);
}

int n, m, a, b, c, ct[maxn << 1];
void dfs(int v, int par)
{
    if(v > n)
        for(int u: T[v])
            ct[u] ++;
    if(v == c)
    {
        puts(ct[b]? "Yes": "No");
        exit(0);
    }
    for(int u: T[v])
        if(u != par)
            dfs(u, v);
    if(v > n)
        for(int u: T[v])
            ct[u] --;
}

int main()
{
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add_edge(G, x, y);
    }
    cnt = n;
    tarjan(1);
    dfs(a, -1);
    return 0;
}

Comparison

Comparison of three solutions:

Solution	Code Length	Running Time	Memory Usage
Max Flow (AC Library)¹	$523~\mathrm{B}$	$337~\mathrm{ms}$	$106480~\mathrm{KB}$
Max Flow (Dinic)²	$1650~\mathrm{B}$	$334~\mathrm{ms}$	$46980~\mathrm{KB}$
Block Forest³	$1142~\mathrm{B}$	$162~\mathrm{ms}$	$57824~\mathrm{KB}$

The block forest solution has the fastest runtime. AC Library implementation offers the shortest code, while manual Dinic uses the least memory.

Personal Note
This problem is excellent—simple statement with rich underlying concepts.
~~I didn’t even think of using max flow during the contest~~