数列的倍增的一个算法题目的求解的过程,如何利用C语言的计算的编程?

Problem Description
Ratish is a young man who always dreams of being a hero. One day his friend Luffy was caught by Pirate Arlong. Ratish set off at once to Arlong's island. When he got there, he found the secret place where his friend was kept, but he could not go straight in. He saw a large door in front of him and two locks in the door. Beside the large door, he found a strange rock, on which there were some odd words. The sentences were encrypted. But that was easy for Ratish, an amateur cryptographer. After decrypting all the sentences, Ratish knew the following facts:

Behind the large door, there is a nesting prison, which consists of M floors. Each floor except the deepest one has a door leading to the next floor, and there are two locks in each of these doors. Ratish can pass through a door if he opens either of the two locks in it. There are 2N different types of locks in all. The same type of locks may appear in different doors, and a door may have two locks of the same type. There is only one key that can unlock one type of lock, so there are 2N keys for all the 2N types of locks. These 2N keys were made N pairs,one key may be appear in some pairs, and once one key in a pair is used, the other key will disappear and never show up again.

Later, Ratish found N pairs of keys under the rock and a piece of paper recording exactly what kinds of locks are in the M doors. But Ratish doesn't know which floor Luffy is held, so he has to open as many doors as possible. Can you help him to choose N keys to open the maximum number of doors?

Input
There are several test cases. Every test case starts with a line containing two positive integers N (1 <= N <= 2^10) and M (1 <= M <= 2^11) separated by a space, the first integer represents the number of types of keys and the second integer represents the number of doors. The 2N keys are numbered 0, 1, 2, ..., 2N - 1. Each of the following N lines contains two integers, which are the numbers of two keys in a pair. After that, each of the following M lines contains two integers, which are the numbers of two keys corresponding to the two locks in a door. You should note that the doors are given in the same order that Ratish will meet. A test case with N = M = 0 ends the input, and should not be processed.

Output
For each test case, output one line containing an integer, which is the maximum number of doors Ratish can open.

Sample Input
3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0

Sample Output
4

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

2
C++语言编程 单调递增最长子序列
1
关于图中所说的斐波那契数列算法复杂度计算的两种准则
1
Python 中数列比较大小的依据是什么?
2
求数列的和,用C语言,谢谢
1
C语言求数列的的第n项的和
1
一个数列递推求解的问题,C语言数据结构怎么解决这个问题呢?
0
等差数列的问题,采用C 语言如何才能进行求解呢??
0
一个数列的递推的问题,怎么利用C语言和数据结构解决,最大值是K^2
2
求解一个和平方数列求和有关的解法的问题,采用C语言解决这个问题的思路实现怎么做?
1
一个数列数组的求和再求比率的问题,如何利用C语言的方法编程算法解决
0
综合运用算法数据结构解决区间交的问题输出答案,C语言应用的问题
0
数列级数的极值的计算的一个问题,请问是如何利用C语言的编程代码实现的呢
0
兔子繁殖的数列的问题,运用C语言的技术如何才能解决的?
0
综合运用C语言的编程的技术如何解决这里的数列求和的算法问题呢
0
数列对的问题,如何运用C语言的方式作答,利用C语言如何解决这个问题
0
请教各位神人看下这里的C语言如何才能高效解决楼梯数列推导的问题
0
数列整数相邻判断的问题,如何利用C语言的功能去实现的
0
KSVD算法中初始化的字典怎么设置?
0
如何利用C语言编程实现对数列的搜索问题,采用C语言代码的编写的方式是怎么做?
0
输出菲波那切数列的第n项,完全按照例子输入和输出结果,可是一直没有写对,哪位大神可以帮我解答一下?