SL苣的集合论
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
到了大一下学期了,SoLo苣和他的同学们一起 ,“被迫”去上离散数学的课程,众所周知,SoLo苣的课堂表现可是超级“好”的,上课“回答”问题相当积极,得到了老师的高度重视,这不,老师看他根骨奇佳,让他来计算集合的复合关系运算:
设A是一个集合,关系集合R和S是集合A上的二元关系,求R与S的复合关系R。S。
如设集合A={1,2,3,4},关系集合R={<1,2>,<3,4>,<2,2>},S= {<4,2>,<2,3>,<3,1>},则R与S的复合为R。S={<1,3>,<2,3>,<3,2>}(详见第一组示例和提示)。
开玩笑嘛,SoLo苣的心思压根不在课堂上,哪里会这个呀,在他的再三恳求下,老师同意让他找一个援兵,他毫不犹豫的选择了你,看着他楚楚可怜的模样,你一定不忍心让他失望吧,你能不能帮他解决问题呢?
Input
输入数据有多组,对于每组输入:
第一行是一个整数n,代表集合A的元素的个数,默认A中的元素为1~n,1<=n<=200;
第二行是一个整数r,代表R的关系元素的个数,1<=r<=n*n;
接下来r行,每行两个数x、y,代表R的第i个关系R[i]{<x,y>};
下一行是一个整数c,代表S的关系元素的个数,1<=c<=n*n;
接下来c行,每行两个数x、y,代表S的第i个关系S[i]{<x,y>}。
第一行是一个整数n,代表集合A的元素的个数,默认A中的元素为1~n,1<=n<=200;
第二行是一个整数r,代表R的关系元素的个数,1<=r<=n*n;
接下来r行,每行两个数x、y,代表R的第i个关系R[i]{<x,y>};
下一行是一个整数c,代表S的关系元素的个数,1<=c<=n*n;
接下来c行,每行两个数x、y,代表S的第i个关系S[i]{<x,y>}。
Output
对于每组样例输出其对应的R。S,每行输出一个关系x,y,中间用空格隔开,输出按照前域从小到大排列;若前域相同,则按照后域从小到大排列(详见示例)。
Sample Input
4 3 1 2 3 4 2 2 3 4 2 2 3 3 1 5 3 1 2 3 4 2 2 4 4 2 2 5 3 1 1 3
Sample Output
1 3 2 3 3 2 1 5 2 5 3 2
Hint
对于关系的复合:设A是一个集合,R和S是集合A上的二元关系,则R与S相同部分得整合即为R与S的复合。换句话说,关系的复合是集合与集合间相同部分的统一化整合,它的定义为
所以,欲求关系的复合。只需前一个集合的后域是后一个集合的前域。
Source
不得不放弃、