你的位置:首页 > ASP.net教程

[ASP.net教程]黑社会团伙(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)。

代码

 

#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