当前位置:首页 > 并查集 > 正文
SSOJ2448团伙
512+

题目大意:n个人,任何两个认识的人不是朋友就是敌人,我朋友的朋友是我的朋友,我敌人的敌人是我的朋友,最多有多少个朋友集合?

题目描述

       在某城市里住着n个人,任何两个认识的人不是朋友就是敌人,而且满足:

(1)我朋友的朋友是我的朋友;

(2)我敌人的敌人是我的朋友。

所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息,即某两个人是朋友,或者某两个人是敌人,请你编写一个程序,计算出这个城市最多可能有多少个团伙?

输入

第1行为n和m,1<n<1000,1<=m<=1000;

以下m行,每行为p,x,y,p的值为0或1,p为0时,表示x和y是朋友,p为1时,表示x和y是敌人。两个整数之间用一个空格隔开。

输出

一个整数,表示这n个人最多可能有几个团伙。

样例输入

6 4
1 1 4
0 3 5
0 4 6
1 1 2

样例输出

3

解题思路

如果两个人是朋友,直接用并查集合并在一起;如果两个人是敌人,就将敌人的敌人合并在一起。关键是敌人的敌人怎么合并?如果只有一个敌人,不需要合并;如果有两个敌人,就把这两个敌人合并在一起;如果有k个敌人,由于之前k-1个敌人已经合并在一起,只需要将第k个敌人和之前k-1个中的任意一个敌人合并即可。

程序1中,f记录敌人的父亲/祖先,d记录敌人。如果不想开敌人数组,还可以将f数组开大一点,用i+n表示敌人,这样如果p和q是敌人,只需要将p和q+n合并在一起、p+n和q合并在一起。由于最后统计有多少个团伙,只统计n个人中有多少个自己是祖先,故程序2中,合并敌人时,必须让编号小的做祖先(前n个点做祖先)。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,

SSOJ2448团伙:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter