((((((((((((((((((((((((((((((((((((((((((((((((((((((((((强化16题解((((((((((((((((((((((((((((((((((((((((((((((((((((((
家庭问题(family)
题目描述
有n 个人,编号为1,2,……n,另外还知道存在K 个关系。一个关系的表达为二元组(α,β)形式,表示α,
β为同一家庭的成员。
问题:当n,k 和k 个关系给出之后,求出其中共有多少个家庭、最大的家庭中有多少人?
例如:
n=6,k=3,三个关系为(1,2),(1,3),(4,5)
此时,6 个人组成三个家庭,即:{1,2,3}为一个家庭,{4,5}为一个家庭,{6}单独为一个家庭,fami
ly 第一个家庭的人数为最多。
输入
文件的第一行为n,k 二个整数(1≤n≤100,k<=2000)(用空格分隔)
接下来的k 行,每行二个整数(用空格分隔)表示关系
输入
第一行为n,k 二个整数(1≤n≤100,k<=2000)(用空格分隔)
接下来的k 行,每行二个整数(用空格分隔)表示关系
输出
二个整数(分别表示家庭个数和最大家庭人数)
嗯嗯这个题我发现我没有先判断这两个人是否已经在一个家庭了,于是就改了一下
很简单的并查集操作。
如果数据范围大一点可能要用到离散化(?),但是数据范围比较小。最后数家庭个数和每个家庭人数就暴力了。
1 /* 2 写代码人:zx 3 批注人:zx 4 指导老师:gg 5 感谢sln大佬提供的代码参考/ 6 */ 7 #include<cstdio> 8 using namespace std; 9 int fa[105]; 10 int jt[105]; 11 int getf(int v) //找爸爸不解释 12 { 13 if(fa[v] == 0) return v; 14 else{ 15 return fa[v] = getf(fa[v]); 16 } 17 } 18 int maxn(int a,int b) //我永远不信任c++自带的max函数 19 { 20 if(a > b) return a; 21 else return b; 22 } 23 int main() 24 { 25 //freopen("family.in","r",stdin); 26 //freopen("family.out","w",stdout); 27 int n,k; 28 int a,b; 29 int t = 0; 30 int ans = 0; 31 scanf("%d%d",&n,&k); 32 for(int i = 1;i <= k;i++){ 33 scanf("%d%d",&a,&b); 34 if(getf(a) != getf(b)) //如果不在一个家庭,就放在一个家庭 35 fa[b] = a; 36 37 } 38 for(int i = 1;i <= n;i++){ 39 for(int j = 1;j <= n;j++){ 40 if(getf(i) == j){ 41 jt[getf(i)]++; //因为数据范围比较小所以犯懒了√ 42 break; 43 } 44 } 45 46 } 47 for(int i = 1;i <= n;i++){ 48 if(jt[i] != 0){ 49 t++; 50 ans = maxn(ans,jt[i]); //√ 51 } 52 } 53 printf("%d %d",t,ans); 54 return 0; 55 }
1195: 亲戚(relation)
题目描述
或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表
姐的孙子。如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近
公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。在这种
情况下,最好的帮手就是计算机。为了将问题简化,你将得到一些亲戚关系的信息,如Marry
和Tom 是亲戚,Tom 和Ben 是亲戚,等等。从这些信息中,你可以推出Marry 和Ben 是亲戚。
请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。
输入
输入由两部分组成。
第一部分以N,M 开始。N 为问题涉及的人的个数,M 表示已经知道M 对亲戚关1<=N,M<=100000,
接下来M 行,每行有两个数ai, bi,表示已知ai 和bi 是亲戚。这些人的编号为1,2,3,…, N。接下来
输入一个整数P(1<=P<=100000),表示有P 次询问,接下来P 行,每行为ci, di,表示询问ci 和di
是否为亲戚。
输出
若ci 和di 为亲戚,则输出“Yes”,否则输出“No”。
这道题我好像犯了和刚才那个题一样的毛病……
1 /* 2 写代码人:zx 3 批注人:zx 4 指导老师:gg 5 感谢raq大佬提供的代码参考/ 6 */ 7 #include<cstdio> 8 using namespace std; 9 int fa[100005]; 10 int getf(int v) 11 { 12 if(fa[v] == 0) return v; 13 else{ 14 return fa[v] = getf(fa[v]); 15 } 16 } 17 int main() 18 { 19 freopen("relation.in","r",stdin); 20 freopen("relation.out","w",stdout); 21 int m,n,p; 22 int a,b; 23 scanf("%d%d",&m,&n); 24 for(int i = 1;i <= n;i++){ 25 scanf("%d%d",&a,&b); 26 if(getf(a) != getf(b)) fa[b] = a; 27 28 } 29 scanf("%d",&p); 30 for(int i = 1;i <= p;i++){ 31 scanf("%d%d",&a,&b); 32 if(getf(a) == getf(b)) printf("Yes "); 33 else printf("No "); 34 } 35 return 0; 36 }
家谱那道题就不放上来了……反正不会……
神tm我最后一句话说有人影响我心情还被gg发现了叫出去谈了一会人生