#PQJ124x564. QOJ 124_564

    ID: 2578 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2017图论模拟

QOJ 124_564

第二轮第二试 魔法 魔法 【故事背景】 JYY 最近从朋友那里获得了一本魔法书,现在他正在练习里面的JSOI 魔法。 【问题描述】 JSOI 魔法施放过程是这样的:有一个左右各有𝑁和𝑀个点的二分图构成一个 魔法阵,左边𝑁个点由0到𝑁−1标号,右边𝑀个点由0到𝑀−1标号。初始时这个 二分图已经有了𝐾个连接(每个连接相当于二分图的一条无向边)。 施法分为从0 开始编号的若干轮,在第𝑖轮中,将会添加一条从左边编号为 𝒊 𝒎𝒐𝒅 𝑵的点到右边编号为𝒊 𝒎𝒐𝒅 𝑴的点的连接。这个过程将会一直继续下去直 到整个二分图节点都能通过连接互通(即二分图连通)。此时魔法阵会被激活, JSOI 就会送你一个萌萌哒的Accept! JYY 想知道对于给定的初始条件,魔法阵激活所需的轮数(即加入的边数)。
【输入格式】 从文件magic.in 中读入数据。 第一行三个正整数𝑁、𝑀、𝐾,表示二分图左边、右边的点数和初始的边数。 接下来𝐾行,每行两个整数𝑢7、𝑣7。表示初始时存在从左边标号𝑢7到右边标 号𝑣7的一个连接。 【输出格式】 输出到文件magic.out 中。 输出一个整数,表示一共进行的轮数。JSOI 保证魔法阵一定能被激活。
【样例输入】 3 5 2 1 3 2 0 【样例输出】 5 【数据规模】 对于20%的数据满足𝑁, 𝑀≤105; 对于另外20%的数据满足𝐾= 0; 对于100%的数据满足1 ≤𝑁, 𝑀≤100, 0 ≤𝐾≤10,000。