关键词：
一言不合先贴题目
Description
Input
Output
Sample Input
4
E 1 4
F 3 5
F 4 6
E 1 2
Sample Output
HINT
{1},{2,4,6},{3,5}
一开始的想法和ABC野兽那道题一样，可以维护每个点和祖先的关系。而且似乎更简单。于是有了下面的程序
#include<iostream> #include<cstdio> using namespace std; int fa[1010],deep[1010],ans[1010][2],n,m; int getf(int k){ if(fa[k]!=k){ int t=fa[k]; fa[k]=getf(fa[k]); deep[k]=deep[k]+deep[t]; deep[k]=deep[k]%2; } return fa[k]; } int main(){ cin>>n>>m; for(int i=1;i<=n;++i){ fa[i]=i; deep[i]=0; } for(int i=1;i<=m;++i){ char c[2]; int x,y; scanf("%s%d%d",&c,&x,&y); if((c[0]==‘1‘)&&(getf(x)!=getf(y))){ int fx=getf(x); int fy=getf(y); deep[fx]=(deep[y]-deep[x]+3)%2; fa[fx]=fy; } if((c[0]==‘0‘)&&(getf(x)!=getf(y))){ int fx=getf(x); int fy=getf(y); deep[fx]=(deep[y]-deep[x]+2)%2; fa[fx]=fy; } } for(int i=1;i<=n;++i){ fa[i]=getf(i); //cout<<fa[i]<<" "<<deep[i]<<endl; ans[fa[i]][deep[i]]++; } int add=0; for(int i=1;i<=n;++i) for(int j=0;j<=1;++j)if(ans[i][j]>0){ add++; } cout<<add; return 0; }
然后、、、、、、就爆0了。
哪里出了问题？忽然发现题设中并没有：我的敌人的朋友是我的敌人。MDZZ！这不符合逻辑啊，虽然NOI从来不讲逻辑。
重新出发，想到分点的方法。通过朋友相关联的，fa[x]=y;通过敌人相关联的，fa[x]=y+n,fa[x+n]=y。该题完美解决。楼下程序：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m,ans,a[1010]; int fa[2020]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x);y=Find(y); if(x==y) return ; fa[x]=y; } int main(){ int i,x,y; char p[10]; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%s%d%d",p,&x,&y); if(p[0]==‘F‘) Union(x,y); else Union(x,y+n),Union(x+n,y); } for(i=1;i<=n;i++) a[i]=Find(i); sort(a+1,a+n+1); for(i=1;i<=n;i++) if(i==1||a[i]!=a[i-1]) ++ans; cout<<ans<<endl; return 0; }
To be continue......
并查集bzoj1370-[baltic2003]gang团伙
【题目大意】在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋... 查看详情
bzoj1370[baltic2003]gang团伙：并查集虚点
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1370题意： 在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： （1）我朋友的朋友是我的朋友。 （2）我敌人的敌人是我的朋友。 所... 查看详情
p1892[boi2003]团伙并查集(代码片段)
题目描述1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅... 查看详情
[并查集]团伙
题号：ZHOJ1258思路：并查集。给每个人建立一个“正集”（朋友）、一个“反集”（敌人），反集要么为空、要么指向一个正集，维护这两类集合，最后统计“正集”的个数。1#include<cstdio>2#include<cstring>... 查看详情
并查集团伙
[codevs2597]团伙 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold 题目描述 Description1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：... 查看详情
并查集学习笔记
并查集是用来查询、合并的有力工具。并查集是用来查询、合并的有力工具。 查看详情
团伙（并查集经典）
题目大体的说：1.我朋友的朋友是我的朋友； 2.我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可... 查看详情
动规(18)-并查集基础题——团伙
在某城市里住着N个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息&#... 查看详情
动规(18)-并查集基础题——团伙(代码片段)
在某城市里住着N个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息&#... 查看详情
动规(18)-并查集基础题——团伙(代码片段)
在某城市里住着N个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息&#... 查看详情
[洛谷p1892]团伙
...人就不在，现在给出一关系，问最多有多少团伙。题解：并查集，建反集，如果是朋友，就把他们的并查集合并；如果是敌人，就把他们分别和对方的反集合并，统计最后有几个联通块C++Code：#include<cstdio>usingnamespacestd;constin... 查看详情
日常学习并查集+mapcodevs2639约会计划题解
然而我居然让诸城一中悲剧机房的C++可以编译了···直接上题目题目描写叙述Descriptioncc是个超级帅哥，口才又好。rp极高（这句话似乎降rp），又非常的幽默，所以非常多mm都跟他关系不错。然而。最关键的是，cc可以... 查看详情
动规(20)-并查集基础题——打击犯罪(代码片段)
【问题描述】 某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情
动规(20)-并查集基础题——打击犯罪(代码片段)
【问题描述】 某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情
动规(20)-并查集基础题——打击犯罪(代码片段)
【问题描述】 某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形... 查看详情
并查集的一般操作③
RT 题目描述 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是： 我朋友的朋友是我的朋友； 我敌人的敌人也是我的朋友。 两个强盗是同... 查看详情
并查集
并查集是一个非常非常简单，好背，但不好理解的题目，但只要理解了，闭着眼都能打出来，当然我也因为这个困扰了好长时间，接下来我给大家说说并查集支持的许多操作。1：找爸爸（find）不要在意名字，这不是帮你理解吗... 查看详情
杭电1213题解：一道最基础的并查集问题
ProblemDescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweachother,andallthefriendsdono 查看详情