[蓝桥杯 2017 国 C] 合根植物

Luogu
IDLGP8654
Time1000ms
Memory256MB
DifficultyP3
2017并查集蓝桥杯国赛
w 星球的一个种植园,被分成 $m \times n$ 个小格子(东西方向 $m$ 行,南北方向 $n$ 列)。每个格子里种了一株合根植物。 这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗? ## Input 第一行,两个整数 $m$,$n$,用空格分开,表示格子的行数、列数($1<m,n<1000$)。 接下来一行,一个整数 $k$,表示下面还有 $k$ 行数据 $(0<k<10^5)$。 接下来 $k$ 行,每行两个整数 $a$,$b$,表示编号为 $a$ 的小格子和编号为 $b$ 的小格子合根了。 格子的编号一行一行,从上到下,从左到右编号。 比如:$5 \times 4$ 的小格子,编号: ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ``` ## Output 一行一个整数,表示答案 [samples] ## Note ## 样例解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/9q0xulxh.png) 时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
Samples
Input #1
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
Output #1
5
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2017 国 C] 合根植物",
    "description": {
      "content": "w 星球的一个种植园,被分成 $m \\times n$ 个小格子(东西方向 $m$ 行,南北方向 $n$ 列)。每个格子里种了一株合根植物。 这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8654"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "w 星球的一个种植园,被分成 $m \\times n$ 个小格子(东西方向 $m$ 行,南北方向 $n$ 列)。每个格子里种了一株合根植物。\n\n这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。\n\n如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?\n\n## Input\n\n第一行,两个整数 $m$,$n$,用空格分开,表示格子的行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments