在一个社区里每个人都有自己的小圈子还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里于是要请你统计一下在一个给定社区中到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。输入格式:输入在第一行给出一个正整数N≤10 4 是已知小圈子的个数。随后N行每行按下列格式给出一个小圈子里的人:K P1 P2 ⋯ PK其中K是小圈子里的人数Pii=1⋯K是小圈子里每个人的编号。这
该程序使用并查集的思想来统计互不相交的部落以及检查两个人是否属于同一个部落。
首先,定义了一个大小为10010的father数组,用来保存每个人的父节点。初始化时,将每个人的父节点设为自己。
然后,通过输入读取小圈子的信息。对于每个小圈子,先读取小圈子的人数k和第一个人的编号first。将第一个人的编号加入到total集合中,并将第一个人的编号与后面的人的编号通过uniont函数进行合并。若k为1,则说明该小圈子只有一个人,不需要进行合并操作。
接下来,遍历total集合,将每个人的父节点加入到cnt集合中,用于统计互不相交的部落数量。
然后,输出total集合的大小(即社区中的人数)和cnt集合的大小(即互不相交的部落数量)。
最后,通过输入读取查询次数m,然后依次读取每对被查询的人的编号a和b。通过find函数判断a和b是否属于同一个部落,若属于同一个部落,则输出"Y",否则输出"N"。
该程序没有使用文件操作或数据库操作。
原文地址: http://www.cveoy.top/t/topic/iRWA 著作权归作者所有。请勿转载和采集!