i589: Forbidden Cities
Tags : 圖論
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-18 22:24

Content

There are $n$ cities and $m$ roads between them. Kaaleppi is currently in city $a$ and wants to travel to city $b$.

However, there is a problem: Kaaleppi has recently robbed a bank in city $c$ and can't enter the city, because the local police would catch him. Your task is to find out if there is a route from city $a$ to city $b$ that does not visit city $c$.

As an additional challenge, you have to process $q$ queries.

有 $n$ 個城市,以 $m$ 條雙向道路連接。肯肯肯在城市 $a$,並且他想到達城市 $b$。

但是有一個問題:肯肯肯最近在城市 $c$ 搶銀行了,被當地的警察通緝,於是他無法到達城市 $c$。你要幫肯肯肯找出有沒有一條由 $a$ 到 $b$,且不經過城市 $c$ 的路徑。

你總共要處理 $q$ 次詢問。(不保證 $a ≠ b, b ≠ c, c ≠ a$,儘管原題敘有說它們會相異,但還是出現了不相異的測資)

Input

第一行有三個正整數 $n, m, q$,代表有 $n$ 個城市,$m$ 條道路,$q$ 筆詢問。城市編號為 $1\sim n$。

接下來 $m$ 行,每行有兩個正整數 $a, b$,代表城市 $a, b$ 之間有一條雙向道路。

接下來 $q$ 行,每行有三個正整數 $a, b, c$,代表詢問你是否有一條連接 $a, b$ 的路徑可以不經過 $c$。

你可以假設每個城市都可以互相到達。

  • $1 \leq n \leq 10^5$
  • $1 \leq m \leq 2 \times 10^5$
  • $1 \leq q \leq 10^5$
  • $1 \leq a, b, c \leq n$
Output

對於每筆詢問,如果存在一條路徑,輸出 $\text{YES}$,否則輸出 $\text{NO}$。

Sample Input #1
5 6 3
1 2
1 3
2 3
2 4
3 4
4 5
1 4 2
3 5 4
3 5 2
Sample Output #1
YES
NO
YES
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (7%): 2.0s , <1K
公開 測資點#1 (7%): 2.0s , <1K
公開 測資點#2 (7%): 2.0s , <1K
公開 測資點#3 (7%): 2.0s , <1K
公開 測資點#4 (8%): 2.0s , <1K
公開 測資點#5 (8%): 2.0s , <1K
公開 測資點#6 (8%): 2.0s , <10M
公開 測資點#7 (8%): 2.0s , <10M
公開 測資點#8 (8%): 2.0s , <10M
公開 測資點#9 (8%): 2.0s , <10M
公開 測資點#10 (8%): 2.0s , <1M
公開 測資點#11 (8%): 2.0s , <1K
公開 測資點#12 (8%): 2.0s , <1K
Hint :

$100\%:無特別限制$

Tags:
圖論
出處:
CSES1705 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」