D. FreeDiv

Codeforces

IDCF73D

Time5000ms

Memory256MB

Difficulty—

dfs and similargraphsgreedy

English · Original

Chinese · Translation

Formal · Original

Vasya plays FreeDiv. In this game he manages a huge state, which has _n_ cities and _m_ two-way roads between them. Unfortunately, not from every city you can reach any other one moving along these roads. Therefore Vasya decided to divide the state into provinces so that in every province, one could reach from every city all the cities of the province, but there are no roads between provinces. Unlike other turn-based strategies, in FreeDiv a player has the opportunity to build tunnels between cities. The tunnels are two-way roads along which one can move armies undetected by the enemy. However, no more than one tunnel can be connected to each city. As for Vasya, he wants to build a network of tunnels so that any pair of cities in his state were reachable by some path consisting of roads and a tunnels. But at that no more than _k_ tunnels are connected to each province (otherwise, the province will be difficult to keep in case other provinces are captured by enemy armies). Vasya discovered that maybe he will not be able to build such a network for the current condition of the state. Maybe he'll have first to build several roads between cities in different provinces to merge the provinces. Your task is to determine the minimum number of roads Vasya needs to build so that it was possible to build the required network of tunnels in the resulting state. ## Input The first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _k_ ≤ 106, 0 ≤ _m_ ≤ 106). Each of the next _m_ lines contains two integers. They are the numbers of cities connected by a corresponding road. No road connects city to itself and there is at most one road between each pair of cities. ## Output Print a single number, the minimum number of additional roads. [samples] ## Note In the first example only one province exists, so it is not necessary to build any tunnels or roads. In the second example two provinces exist. It is possible to merge the provinces by building a tunnel between cities 1 and 3. In the third example at least one additional road is necessary. For example it is possible to build additional road between cities 1 and 2 and build two tunnels between cities 1 and 3, 2 and 4 after that.

Vasya 玩 FreeDiv 游戏。在游戏中，他管理一个拥有 #cf_span[n] 座城市和 #cf_span[m] 条双向道路的庞大国家。不幸的是，并非每座城市都能通过这些道路到达其他任何城市。因此，Vasya 决定将国家划分为若干省份，使得每个省份内，任意两座城市均可通过道路互相到达，且省份之间不存在任何道路。与其它回合制策略游戏不同，在 FreeDiv 中，玩家可以在城市之间修建隧道。隧道是双向道路，军队可以通过它们隐蔽移动。然而，每座城市最多只能连接一条隧道。Vasya 希望建立一个隧道网络，使得国家中任意两座城市都能通过道路和隧道的组合路径互相到达。但同时，每个省份连接的隧道数量不得超过 #cf_span[k] 条（否则，若其他省份被敌军占领，该省份将难以坚守）。 Vasya 发现，对于当前国家的状况，可能无法构建出所需的隧道网络。他可能需要先在不同省份的城市之间修建若干条道路，以合并省份。你的任务是确定 Vasya 最少需要修建多少条额外道路，才能使得在最终状态下能够构建出所需的隧道网络。第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106]）。接下来的 #cf_span[m] 行每行包含两个整数，表示由一条道路连接的两座城市编号。没有道路连接城市到自身，且任意两座城市之间至多有一条道路。请输出一个整数，表示最少需要修建的额外道路数量。在第一个例子中，仅存在一个省份，因此无需修建任何隧道或道路。在第二个例子中，存在两个省份。可以通过在城市 1 和 3 之间修建一条隧道来合并这两个省份。在第三个例子中，至少需要修建一条额外道路。例如，可以在城市 1 和 2 之间修建一条额外道路，之后再在城市 1 和 3、2 和 4 之间各修建一条隧道。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106]）。接下来的 #cf_span[m] 行每行包含两个整数，表示由一条道路连接的两座城市编号。没有道路连接城市到自身，且任意两座城市之间至多有一条道路。 ## Output 请输出一个整数，表示最少需要修建的额外道路数量。 [samples] ## Note 在第一个例子中，仅存在一个省份，因此无需修建任何隧道或道路。在第二个例子中，存在两个省份。可以通过在城市 1 和 3 之间修建一条隧道来合并这两个省份。在第三个例子中，至少需要修建一条额外道路。例如，可以在城市 1 和 2 之间修建一条额外道路，之后再在城市 1 和 3、2 和 4 之间各修建一条隧道。

**Definitions** Let $ n, m, k \in \mathbb{Z} $ with $ 1 \leq n, k \leq 10^6 $, $ 0 \leq m \leq 10^6 $. Let $ G = (V, E) $ be an undirected graph with $ |V| = n $ vertices and $ |E| = m $ edges. Let $ C_1, C_2, \dots, C_p $ be the connected components (provinces) of $ G $, where $ p \geq 1 $ is the number of components. Let $ s_i = |C_i| $ denote the size of component $ C_i $. **Constraints** 1. Each vertex may have at most one tunnel incident to it. 2. Each connected component $ C_i $ may have at most $ k $ tunnels incident to its vertices in total (i.e., the sum of tunnel degrees across all vertices in $ C_i $ is at most $ k $). 3. Tunnels may only be built between vertices in *different* components. 4. Additional roads may be built between any two vertices in *different* components to merge them. **Objective** Find the minimum number of additional roads to build so that, after merging components via these roads, the resulting graph admits a tunnel assignment satisfying: - Each vertex has at most one tunnel. - Each merged component has at most $ k $ total tunnel endpoints. - The entire graph becomes connected via roads and tunnels (i.e., the union of roads and tunnels forms a connected graph). **Note**: The goal is to achieve a single connected component via a combination of *additional roads* and *tunnels*, under the constraints on tunnel usage per vertex and per component.

Samples

Input #1

Output #1

Input #2

4 2 2
1 2
3 4

Output #2

Input #3

4 0 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. FreeDiv",
    "description": {
      "content": "Vasya plays FreeDiv. In this game he manages a huge state, which has _n_ cities and _m_ two-way roads between them. Unfortunately, not from every city you can reach any other one moving along these ro",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF73D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya plays FreeDiv. In this game he manages a huge state, which has _n_ cities and _m_ two-way roads between them. Unfortunately, not from every city you can reach any other one moving along these ro...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 玩 FreeDiv 游戏。在游戏中，他管理一个拥有 #cf_span[n] 座城市和 #cf_span[m] 条双向道路的庞大国家。不幸的是，并非每座城市都能通过这些道路到达其他任何城市。因此，Vasya 决定将国家划分为若干省份，使得每个省份内，任意两座城市均可通过道路互相到达，且省份之间不存在任何道路。\n\n与其它回合制策略游戏不同，在 FreeDiv 中，玩家可以在城市之间修建隧道...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z} $ with $ 1 \\leq n, k \\leq 10^6 $, $ 0 \\leq m \\leq 10^6 $.  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $ vertices and $ |E| = m $ edges.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments