2597 团伙

题目描述 Description

1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他们要么是朋友,要么是敌人。而且有一点是肯定的,就是:

我朋友的朋友是我的朋友;

我敌人的敌人也是我的朋友。 

两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息,问你最多有多少个强盗团伙。

输入描述 Input Description

输入文件gangs.in的第一行是一个整数N(2<=N<=1000),表示强盗的个数(从1编号到N)。 第二行M(1<=M<=5000),表示关于强盗的信息条数。 以下M行,每行可能是F p q或是E p q(1<=p q<=N),F表示p和q是朋友,E表示p和q是敌人。输入数据保证不会产生信息的矛盾。

输出描述 Output Description

输出文件gangs.out只有一行,表示最大可能的团伙数。

样例输入 Sample Input

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

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

2<=N<=1000

1<=M<=5000

1<=p q<=N

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 long fa[1001],a[1001][1001],c[1001];
 8 long find(long x)
 9 {
10     long r;
11     r=x;
12     while (fa[r]!=r) r=fa[r];
13     return r;
14 }
15 int main()
16 {
17     long n,m,s=0,i,j,k,x,y,r1,r2,t;
18     char z;
19     cin>>n>>m;
20     memset(a,0,sizeof(a));
21     for (i=1; i<=n; i++) 
22     fa[i]=i;
23     for (i=1; i<=m; i++)
24     {
25         cin>>z>>x>>y;
26         if (z=='F') 
27         {
28             r1=find(x); 
29             r2=find(y);  
30             fa[r2]=r1;     
31         }
32         if (z=='E') // x,y为敌对关系 
33         {
34             for (j=1; j<=a[x][0]; j++) //a[x][0]为x敌人的数量 
35             {
36                r1=find(y); 
37                r2=find(a[x][j]); 
38                fa[r2]=r1; 
39             }
40             for (j=1; j<=a[y][0]; j++)
41             {
42                r1=find(x); 
43                r2=find(a[y][j]); 
44                fa[r2]=r1; 
45             }  
46             a[x][0]++; 
47             a[y][0]++;
48             a[x][a[x][0]]=y;    
49             a[y][a[y][0]]=x;     
50         }
51     }    
52     s=0; 
53     for (i=1; i<=n; i++)    
54     if (fa[i]==i) 
55     s++;
56     cout<<s;
57 }
58     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏学习力

《Java从入门到放弃》框架入门篇:spring中AOP的配置方式

21611
来自专栏晨星先生的自留地

一次freebuf溯源引发的木马后门分析

2154
来自专栏微信公众号:Java团长

Java基础05 实施接口

在Java基础04 封装与接口中,private关键字封装了对象的内部成员。经过封装,产品隐藏了内部细节,只提供给用户接口(interface)。

912
来自专栏大数据文摘

史上最强算法论战:请不要嘻哈,这是哈希

2596
来自专栏阮一峰的网络日志

Javascript的10个设计缺陷

前几篇文章,我经常说Javascript的设计不够严谨,有很多失误。 今天的这一篇,前半部分就谈为什么会这样,后半部分将列举Javascript的10个设计缺陷...

3647
来自专栏编程一生

架构师之路--从原理角度来分析性能

  埃及艳后Cleopatra,很小的时候看过妈妈买的一本书里把她的名字翻译成克娄巴特拉,里面有很多描写她美貌的场景描写。然而这个以美貌著称的奇女子,我看到书里...

942
来自专栏北京马哥教育

shell十三问,为linux学习打基础(三)

本文整理并转自CU上的帖子[学习共享] shell 十三問?,此贴是2003年发表的,但却是相当不错的linux基础知识汇集贴,原帖主使用的台湾风格,本文加以简...

3856
来自专栏数据结构与算法

BZOJ3669: [Noi2014]魔法森林(瓶颈生成树 LCT)

为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始...

1253
来自专栏后端技术探索

php进阶

基本数据类型和数组都为真复制,即为真副本,当属性为对象时,为假复制,改变副本仍会影响原对象.解决方案:

1621
来自专栏小樱的经验随笔

Vijos P1113 不高兴的津津【模拟】

不高兴的津津 描述 津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢...

2658

扫码关注云+社区

领取腾讯云代金券