896 . 隨機演算法 2（駭客題）
TopCoder
Tags
Description
為了慶祝自己通過了隨機演算法這門課，你決定用在這堂課所學通過以下題目：
給定一張 $n$ 個點 $m$ 條邊的簡單無向圖，請回答從點 $1$ 出發是否能經過一連串的道路抵達點 $n$。
$2 \leq n \leq 2000, 0 \leq m \leq \frac{n(n - 1)}{2}$
對此問題，你寫出了如下的程式碼：
Code
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
const int MAGIC = 8e7;
int main() {
int n, m;
cin >> n >> m;
vector <vector <int>> adj(n + 1);
for (int i = 0, u, v; i < m; ++i) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (adj[1].empty()) {
cout << "No\n";
return 0;
}
bool found = false;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int s = 1;
for (int j = 0; j < MAGIC; ++j) {
s = adj[s][rng() % (int)adj[s].size()];
if (s == n) {
found = true;
break;
}
}
if (found) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
但寫完之後上傳並沒有通過...，你能夠構造出一筆滿足題目條件的測資讓該程式碼 WA 嗎？
Input Format
輸入第一行有兩個整數 $n, m$，代表圖的點數與邊數。
接下來 $m$ 行每行有兩個整數 $u_i, v_i$，代表點 $u_i$ 與點 $v_i$ 之間有一條無向邊連接。
- $2 \leq n \leq 2000$
- $0 \leq m \leq \frac{n(n - 1)}{2}$
- $1 \leq u_i, v_i \leq n$
- 圖為簡單圖，意即：圖沒有自環與重邊
Output Format
若從點 $1$ 出發能經過一連串的道路抵達點 $n$，請輸出 Yes，否則請輸出 No。
Sample Input 1
3 2 1 2 2 3
Sample Output 1
Yes
Sample Input 2
817 0
Sample Output 2
No
Hints
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料：
#include <stdio.h>
int main() {
puts("3 2");
puts("1 2");
puts("2 3");
}
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 無額外限制 | 100 |