TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

給你一張無向圖 $G=(V,E)$(可能有重邊或自環),其中的點從 $1$ 編號到 $N$,請問這張無向圖有幾個連通塊呢?

咦,太難了嗎?我們還保證這張無向圖沒有 degree 為 0 的點喔!

好吧,好像又有點太簡單了。那我們來給一點小限制吧:請把以下這個程式的所有底線換成任何 ASCII 值介於 32 到 126 之間的字元,使得它能解決這個問題!

#include <bits/stdc++.h>

using namespace std;

#define b stoi
int p[801];
int n, d, a, r;
stringstream s;
string y;

void c() { s.str(""); s.clear(); }

int CountConnectedComponent(string x) {
  ______r(__a__b(_d___ _*_?_n_[_d__]__n)?_(_*_)__1__.____n__a_);
  do ___,_=r_____r___a___x_r___1_2__4_3___while(_!=_);
  return________.begin(),_.end()______;
}

int main() {
  cin >> n >> d;
  y = string(istreambuf_iterator<char>(cin), {});
  cout << CountConnectedComponent(y) << endl;
}

別忘了看下面的提示喔!

Input Format

輸入第一行有兩個以空白隔開的整數 $N,M$,分別代表這張圖有幾個點和幾個邊。

接下來有 $M$ 行,每行有兩個以空白隔開的整數 $a_i,b_i$,代表有一條無向邊連接編號為 $a_i,b_i$ 的點。

對於所有測資,$1\leq N,M\leq 200$。測資中所有的換行都是 LF('\n')。

Output Format

請輸出一行包含一個整數,代表這張圖總共有幾個連通塊。

Sample Input

5 6
1 2
2 3
3 3
3 1
5 4
4 5

Sample Output

2

Hints

  1. 出題者平常寫 code 的時候不會用#include <bits/stdc++.h>using namespace std;。既然在題目中出現了,是不是代表著出題者想要隱藏什麼不可告人的祕密呢?
  2. 你平常絕對不會這樣求連通塊數量,所以請跳脫框架思考(?
  3. 有些宣告的變數可能根本不會用到喔!
  4. ASCII 32~126 也包含空白和底線喔!
  5. 題目中幾乎每個條件都是有用的!
  6. Code 請不要有多餘的空行或空白,否則會被判定為 WA。(你的 code length 會是 484 bytes。)
  7. 這些提示真的很重要喔!

Problem Source

Subtasks

No. Testdata Range Score
1 0~13 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 262144 262144 1
1 2500 262144 262144 1
2 2500 262144 262144 1
3 2500 262144 262144 1
4 2500 262144 262144 1
5 2500 262144 262144 1
6 2500 262144 262144 1
7 2500 262144 262144 1
8 2500 262144 262144 1
9 2500 262144 262144 1
10 2500 262144 262144 1
11 2500 262144 262144 1
12 2500 262144 262144 1
13 2500 262144 262144 1