当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > 黑社会团伙(gangs),黑社会团伙gangs

黑社会团伙(gangs),黑社会团伙gangs

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

黑社会团伙(gangs),黑社会团伙gangs

题目描述

      众所周知,香港的黑社会组织猖獗,警方希望能摸清他们的内部构成情况,特派小生前往调查。经过长期的卧底,小生初步获得了一些资料:整个组织有 n 个人,任何两个认识的人不是朋友就是敌人。

而且满足:①我朋友的朋友是我的朋友;②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。

      现在,警方委派你协助调查,拥有关于这 n 个人的 m 条信息(即某两个人是朋友,或某两个人是敌人) ,请你计算出这个城市最多可能有多少个团伙。

 

数据范围

2≤N≤2000,1≤M≤5000。

输入输出格式

输入描述:

第一行包含一个整数 N,第二行包含一个整数 M,接下来 M 行描述 M 条信息。

内容为以下两者之一:“F x y”表示 x 与 y 是朋友;“E x y”表示 x 与 y 是敌人(1≤x≤y≤N) 。

输出描述:

包含一个整数,即可能的最大团伙数。

输入输出样例

输入样例:

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出样例:

3

思路

并查集。用1—n表示朋友,若p[0]==F,则unionn(x,y);用n 1—2*n表示敌人,若p[0]==E,则unionn(x,y n),unionn(y,x n)。

代码

 

图片 1#include<stdio.h> #include<string.h> int a[5000]; char p[10]; int find(int x) { if(a[x]!=x) x=find(a[x]); return a[x]; } void unionn(int x,int y) { x=find(x); y=find(y); a[y]=x; } int main() { int n,m,x,y,i,j,z,k=0; scanf("%d%d",&n,&m); for(i=1;i<=n*2;i ) a[i]=i; for(i=1;i<=m;i ) { scanf("%s%d%d",p,&x,&y); if(p[0]=='F') unionn(x,y); if(p[0]=='E') { unionn(x,y n); unionn(y,x n); } } for(i=1;i<=n;i ) a[i]=find(i); for(i=1;i<n;i ) for(j=1;j<=n-i;j ) if(a[j]>a[j 1]) { z=a[j]; a[j]=a[j 1]; a[j 1]=z; } for(i=1;i<=n;i ) if(a[i]!=a[i-1]) k ; printf("%d",k); return 0; } View Code

 

题目描述 众所周知,香港的黑社会组织猖獗,警方希望能摸清他们的内部构成情况,特派小生前往调...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:黑社会团伙(gangs),黑社会团伙gangs

关键词: