并查集1
并查集之
将可以视为一个整体的东西合并(动态维护具有传递性的东西)
[NOI2015]程序自动分析
题目描述
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3...代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
输入输出格式
输入格式：
从文件prog.in中读入数据。
输入文件的第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj；
输出格式：
输出到文件 prog.out 中。
输出文件包括t行。
输出文件的第 k行输出一个字符串“ YES” 或者“ NO”（不包含引号，字母全部大写），“ YES” 表示输入中的第k个问题判定为可以被满足，“ NO” 表示不可被满足。
输入输出样例
输入样例#1：
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1输出样例#1：
NO
YES
输入样例#2：
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
输出样例#2：
YES
NO注意到i,j小于10^9,所以需要离散化一波
发现,x1=x2,x2=x3所以x1=x3 这是具有传递性的
于是我们用并查集维护所有e=1的操作
而x1!=x2,x2!=x3并不代表x1!=x3
所以对于e=0的操作,我们查询i,j在不在一个集合,在那就是NO了
代码
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int fa[N*2],t,n,tot;
struct Node{int x,y,op;}a[N];
int b[N*2],pd;
bool cmp(Node i,Node j){return i.op>j.op;}
int read(){
int cnt=0;char ch=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
return cnt;
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
t=read();
while(t--){
tot=0,pd=0;
memset(fa,0,sizeof(fa));
memset(b,0,sizeof(b));
memset(a,0,sizeof(a));
n=read();
for(int i=1;i<=n;i++){
a[i].x=read(),a[i].y=read(),a[i].op=read();
b[++tot]=a[i].x,b[++tot]=a[i].y;
}
sort(b+1,b+tot+1);//离散化
int cur=unique(b+1,b+tot+1)-b;
for(int i=1;i<=n;i++){
a[i].x=lower_bound(b+1,b+cur+1,a[i].x)-b;
a[i].y=lower_bound(b+1,b+cur+1,a[i].y)-b;
}
for(int i=1;i<=cur;i++) fa[i]=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
int x=find(a[i].x),y=find(a[i].y);
if(a[i].op){
if(x!=y) fa[x]=y;
}
else if(x==y){
cout<<"NO"<<endl;
pd=1;break;
}
}
if(!pd) cout<<"YES"<<endl;
}
}多米诺骨牌
有 n 个多米诺骨牌，从左到右排列，每一个骨牌都有一个高度 Li，向右推倒，它会直接向右倒下，如下图，倒下后该骨牌的顶端落在 Xi+Li 的位置，（Xi 是它位于的坐标，即倒下时该骨牌不会发生移动）
在倒下过程中，骨牌会碰到其他骨牌，碰到的骨牌会向右倒，如下图，最左边的骨牌倒下会碰倒 A,B,C，A,B,C 会倒下，但是不会直接碰到 D，但是 D 会因为 C 的倒下而碰倒。
在给你 N 个骨牌的坐标 Xi，和每个骨牌的高度 Li。则一个骨牌能碰倒另一个骨牌当切仅当 xi+li≥xj。同时有 Q 个询问 [L,R]，问向右推到第 L 个骨牌，最少需要多少代价让 R 倒下。你可以临时增加某个骨牌的高度，增加 1 个高度的代价是 1.
输入样例
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6
输出样例
0
1
1
2
20%数据：N,Q<=1000,Xi<=10000
40%数据：N,Q<=10000,Xi<=100000
100%数据：2<=N<=100000,1<=Q<=2000000,Xi<=10^9
分析
我们倒着处理,把每一个骨牌加入栈中
如果后面加入的区间能覆盖前面的区间
它们可以看做一个整体
所以就用并查集啦,当合为一个整体过后,这个整体的左节点就是最左边的骨牌的位置
(我们只用记录左节点,这样已经可以判断能不能覆盖(推到)了)
所以这道题告诉我们
当数据很多,很繁琐时,用并查集把一些合并成一个,这样会方便处理
然后用后缀和O(1)查询,先看代码吧
#include<bits/stdc++.h>
/*
这题等于是求一段区间内有多少长度没被覆盖
把多米诺骨牌看成区间，按照倒序处理每个区间，看成是每次这个区间与后面的一些区间并成连通块，
处理x为当前区间的查询，这需要知道y属于哪个连通块，用栈+并查集维护，然后再维护一个未覆盖长度的后缀和，
就可以O1来回答询问，并成连通块的时候顺便更新这个后缀和
*/
using namespace std;
#define ll long long
#define N 200010
#define in read()
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
struct Node{
int l,r;
}a[N],b[N];
vector<int>g[N];
int n,m;
stack<int> S;
int fa[N],l[N],r[N];
ll sum[N],ans[N];
int find(int x){
if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];
}
inline void solve(int x,int id){
int tmp=b[id].r;
ans[id]=sum[x]-sum[find(tmp)];
}
int main(){
n=in;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++){
a[i].l=in;
a[i].r=a[i].l+in;
//i骨牌的区间
}
m=in;
for(int i=1;i<=m;i++){
b[i].l=in;b[i].r=in;
g[b[i].l].push_back(i);
}
for(int i=n;i>=1;i--){
l[i]=a[i].l;r[i]=a[i].r;
while(!S.empty() && l[S.top()] <=r[i]){
r[i]=max(r[i],r[S.top()]);
fa[find(S.top())]=i;
S.pop();
}//与栈顶合并一个联通块
if(!S.empty()) sum[i]=sum[S.top()] + l[S.top()]-r[i];//如果栈有元素，说明后面有联通快，则统计后缀和
else sum[i]=0;//后缀和记录是当前点到最后的不联通数量
S.push(i);
int len= g[i].size();
for(int j=0;j<len;j++)//统计当前点做为左端点的询问答案
solve(i,g[i][j]);
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}团伙
题目描述
在某城市里住着 n 个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这 n 个人的 m 条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
输入格式
第 1 行为 n 和 m ，其中 1<n<1000，1<=m<=100000；
以下 m 行，每行为 p x y ，其中 p 的值为 0 或 1 ，p 为 0 时，表示 x 和 y 是朋友，p 为 1 时，表示 x 和 y 是敌人。
输出格式
一个整数，表示这 n 个人最多可能有几个团伙。
样例数据 1
输入 [复制]
6 4
1 1 4
0 3 5
0 4 6
1 1 2
输出
3
备注
【样例说明】
{1}，{2，4， 6}，{3，5} 共 3 个团伙。
分析
朋友的朋友是朋友,具有传递性
敌人的敌人是朋友,具有传递性
#include<bits/stdc++.h>
#define N 1005
using namespace std;
int father[N],enemy[N],m,n,ans=0;
int read()
{
int x=0,p=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')p=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c-'0');
c=getchar();
}
return x*p;
}
int getfather(int x)
{
if(father[x]==x) return x;
else father[x]=getfather(father[x]);
return father[x];
}
void merge(int x,int y)
{
x=getfather(x);
y=getfather(y);
if(x!=y) father[x]=y;
}
int main()
{
//freopen("1.in","r",stdin);
n=read(),m=read();
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
{
int p=read(),x=read(),y=read();
if(p==0) merge(x,y);//朋友的朋友是朋友
else
{
if(enemy[x]) merge(enemy[x],y);//朋友的敌人是朋友
else enemy[x]=y;
if(enemy[y]) merge(enemy[y],x);
else enemy[y]=x;
}
}
for(int i=1;i<=n;i++)//森林中有几个根,就是几个团伙
if(i==getfather(i)){
ans++;
}
cout<<ans;
return 0;
}下一篇： Java 异常 之深究学习(敲详细)