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 条评论
登录 后参与评论

相关文章

  • T7316 yyy的最大公约数(者)

    题目背景 全场基本暴力 题目描述 ? 输入输出格式 输入格式: 如图 输出格式: 如图 输入输出样例 输入样例#1: 如图 输出样例#1: 如图 说明...

    attack
  • P1314 聪明的质监员

    题目描述 小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到n 逐一编号,每个矿石都有自己的重量 以及价值 。检验矿...

    attack
  • 2144 砝码称重 2

     时间限制: 1 s  空间限制: 16000 KB  题目等级 : 钻石 Diamond 题解 题目描述 Description 有n个砝码,现在要称一个质量...

    attack
  • 40个常用的基本Linux命令

    在本教程中,我将展示一些非常基本的Linux命令,并提供一些示例,这些示例能使你更加熟悉Linux命令行。 要成为Linux专家,对于初学者来说,第一步就是开始...

    三分恶
  • 都说 AllenNLP 好用,我们跑一遍看看究竟多好用

    良好学习过程的关键原则之一,就是让学习的内容略高于当前的理解。如果该主题与你已知的内容太过于相似,那么你就不会有很大的进步。另一方面,如果这个主题太难的话,你就...

    AI研习社
  • 几张图看一下Intel和NVIDIA显卡虚拟化

    GPU全虚拟化的方式由于其性能和多虚拟机共享性方面的优势,一直是GPU厂家所努力支持的方向。本文通过几张架构图,看一下GPU全虚拟化中的Intel GVT-g和...

    虚拟化云计算
  • 销售管理者应该关注的业务指标

    CRM可以解决企业很多问题,但最让企业管理者喜欢的应该就是管理报表了,在ERP风靡的年代很多人也习惯叫它管理者驾驶舱。之所以叫管理者驾驶舱是因为管理者可以像驾驶...

    臭豆腐
  • electron窗口间通信

    liulun
  • TESLA V100如何让质疑GPU的流言“失声”

    【IT168 评论】GPU在人工智能来临的前夜火了,很多人的眼光也聚焦到了英伟达身上,随之而来的,流言也就多了起来。有人认为,GPU在人工智能的应用存在一定的局...

    企鹅号小编
  • 苹果maccms最新漏洞修复解决办法

    苹果CMS漏洞是越来越多了,国内很多电影网站都使用的是maccms V10 V8版本,就在2020年初该maccms漏洞爆发了,目前极少数的攻击者掌握了该EXP...

    技术分享达人

扫码关注云+社区

领取腾讯云代金券