L2-013. 红色警报

wang 发表于 并查集 分类,标签: 天梯赛
 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。输入格式:输入在第一行给出两个整数N(0<N<=500)和M(<=5000),分别为城市个数(于是默认城市从0到N-1编号)和连接两城市的通路条数。随后M行,每行给出一条通路所连接的两个城市的编号,其间以1个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数K和随后的K个被攻占的城市的编号。注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。输出格式:对每个被攻占的城市,如果它会改变整个国家的连通性,则输出“RedAlert:Citykislost!”,其中k是该城市的...

L2-010. 排座位(天梯赛)

发表于 并查集 分类,标签: 天梯赛
 布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。输入格式:输入第一行给出3个正整数:N(<=100),即前来参宴的宾客总人数,则这些人从1到N编号;M为已知两两宾客之间的关系数;K为查询的条数。随后M行,每行给出一对宾客之间的关系,格式为:“宾客1宾客2关系”,其中“关系”为1表示是朋友,-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行,每行给出一对需要查询的宾客编号。这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友,朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。输出格式:对每个查询输出一行结果:如果两位宾客之间是朋友,且没有敌对关系,则输出“Noproblem”;如果他们之间并不是朋友...

PAT (Advanced Level)1118. Birds in Forest (25)

发表于 并查集 分类,标签: pat
 Somescientiststookpicturesofthousandsofbirdsinaforest.Assumethatallthebirdsappearinthesamepicturebelongtothesametree.Youaresupposedtohelpthescientiststocountthemaximumnumberoftreesintheforest,andforanypairofbirds,telliftheyareonthesametree.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinecontains...

PAT (Advanced Level)1114. Family Property (25)

发表于 并查集 分类,标签: pat
 Thistime,youaresupposedtohelpuscollectthedataforfamily-ownedproperty.Giveneachperson'sfamilymembers,andtheestate(房产)infounderhis/herownname,weneedtoknowthesizeofeachfamily,andtheaverageareaandnumberofsetsoftheirrealestate.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveintegerN(<...

社交集群(并查集)

发表于 并查集 分类,标签: 天梯赛
 在社交网络平台注册时,用户通常会输入自己的兴趣爱好,以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序,找出所有的集群。输入格式:输入的第一行给出正整数N(<=1000),即社交网络中的用户总数(则用户从1到N编号)。随后N行,每行按下列格式列出每个人的兴趣爱好:Ki:hi[1]hi[2]...hi[Ki]其中Ki(>0)是第i个人的兴趣的数量,hi[j]是第i个人的第j项兴趣的编号,编号范围为[1,1000]内的整数。输出格式:首先在第一行输出整个网络中集群的数量,然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔,行首尾不得有多余空格。输入样例:83: 2 7 101: 42: 5 31: 41: ...