896 . 隨機演算法 2（駭客題）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

coding_pooh

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

50.0% (4/8)

Tags

ioicamp ioicamp-2025

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
Submit
Back to Top