图论系列：
前言：
相关题单：戳我
算法讲解：戳我
代码可能过多啊，到时候页面别卡死了，所以就把代码最前面的缺省源删了（反正就是几个头文件/define int long long，自己加一下即可）。
并查集记得初始化，最小生成树记得排序。
P3367 【模板】并查集
板子题，给定 \(n\) 个元素，有 2 种操作，一种合并，一种询问是否在同一集合内。
唔唔，是算法讲解里并查集的初始化+路径压缩查询+合并操作，也是并查集的基础运用。
代码：
const int M=1e4+5;
int n,q;
int fa[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) fa[i]=i;
int opt,x,y;
while(q--)
{
cin>>opt>>x>>y;
if(opt==1)
{
int a=find(x),b=find(y);
if(a==b) continue;
fa[a]=b;
}
else
{
int a=find(x),b=find(y);
if(a==b) cout<<"Y\n";
else cout<<"N\n";
}
}
return 0;
}
P3366 【模板】最小生成树
板子题。使用 Kruskal 求最小生成树。
按边权大小从小到大排序之后，使用并查集维护当前边连接的两点是否已经在同一个集合内了，如果在就跳过，不在就加入这条边，然后在并查集中将这两点合并起来。
注意图可能存在不连通的情况，所以每成功加入一条边就记录一下，根据树的性质：点数=边数+1，如果加入的边数等于 \(n-1\) 时，就可以输出答案了，此时加入的边已经让图联通了。否则最后输出 orz。
代码：
const int M=2e5+5;
int n,m,ans,num;
int fa[M];
struct edge{
int u,v,w;
inline bool operator <(const edge &o) const
{
return w<o.w;
}//结构体内置排序，实际上就是按边权从小到大排，手写cmp一样的
};edge e[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1);//按边权排序
for(int i=1,x,y;i<=m;i++)
{
x=find(e[i].u),y=find(e[i].v);
if(x==y) continue;
ans+=e[i].w,fa[x]=y,++num;
if(num==n-1)//成功加入 n-1 条边
{
cout<<ans<<"\n";
return 0;
}
}
cout<<"orz\n";
return 0;
}
P3144 [USACO16OPEN] Closing the Farm S
经典trick，在很多包含删除操作的题会用到。给定一张无向图，\(n\) 个点 \(m\) 条边，给定删去点的顺序，每一个点被删的时同时删去与其相连的边。询问在给定顺序的第 \(i-1\) 个点被删去后，剩下的图是否是一张无向连通图（还在的点互相连通）。
并查集虽然可以判断当前存在的集合个数，但是没法处理这种删除的操作（并查集只能处理单点从某个集合移出的操作）。那么考虑正难则反，我们可以将删除的顺序颠倒过来，于是就变成了加边的操作，这时候并查集既可以处理了。
问题转化成，给定一些边，按照顺序加入一些点，观察现在的图是否连通，如何用并查集判断当前有多少个连通块？简单，首先加入一个点肯定就会多一个连通块，但是遍历与其相连的边，如果成功加入 \(x\) 条边，那么连通块就少了 \(x\) 个。
代码：
const int M=2e5+5;
int n,m,res;
int a[M],fa[M],ans[M],vis[M];
int cnt=0;
struct N{
int to,next;
};N p[M<<1];
int head[M];
inline void add(int a,int b)
{
++cnt;
p[cnt].next=head[a];
head[a]=cnt;
p[cnt].to=b;
}
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1,a,b;i<=m;++i) cin>>a>>b,add(a,b),add(b,a);
for(int i=1;i<=n;++i) cin>>a[i],fa[i]=i;
for(int i=n,u,v,fx,fy;i>=1;--i)//反着来
{
u=a[i],res=0,vis[u]=1;//标记当前点已经在图中了
for(int j=head[u];j!=0;j=p[j].next)//遍历与这个点相连的边
{
v=p[j].to;
if(!vis[v]) continue;//如果通过这条边相连的点还没有出现在图中就不管
fx=find(u),fy=find(v);
if(fx!=fy) fa[fx]=fy,++res;//统计成功加入的边数
}
ans[i]=ans[i+1]-res+1;//当前连通块=上一次操作后的连通块-因为我新加的边而减少了res的连通块+一开始我是独立的
}
for(int i=1;i<=n;++i)
{
if(ans[i]==1) cout<<"YES\n";//如果只有一个连通块
else cout<<"NO\n";
}
return 0;
}
P2814 家谱
由于给定的是各个人的名字，所以拿一个 map 将每一个名字映射为一个数，因为最后输出的是名字，再用一个 map，将每个名字映射的数映射回去。查询祖先就是查询当前集合的根。
代码：
const int M=5e4+5;
string s;
int fa[M];
map<string,int> mapp;
map<int,string> str;//两个map负责 名字->数字 数字->名字
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int idx=0,a=0,b=0,q=0;char opt;
for(int i=1;i<M;i++) fa[i]=i;
while(1)
{
cin>>opt;
if(opt=='$') break;
cin>>s;
if(opt=='#')
{
if(!mapp[s]) mapp[s]=++idx,str[idx]=s;//出现了一个新名字
b=mapp[s];
}
else if(opt=='+')//+就是merge的操作，注意题目中给定操作描述说的谁是谁的祖先
{
if(!mapp[s]) mapp[s]=++idx,str[idx]=s;
a=mapp[s];
int x=find(a),y=find(b);
if(x==y) continue;
fa[x]=y;
}
else
{
q=mapp[s];
find(q);
cout<<s<<" "<<str[fa[q]]<<"\n";
}
}
return 0;
}
P1547 [USACO05MAR] Out of Hay S
按照最小生成树一个一个加进去，那么由于边权是按从小到大排序了的，所以最后一条加进去的边就是最小的。（woc，多久前写的了，竟然拿了个变量存加入的边的权值的最大值，有点多此一举了）
代码：
const int M=1e4+5;
int n,m,tot,maxx;
int fa[M];
struct N{
int u,v,w;
};N p[M];
inline bool cmp(N a,N b) {return a.w<b.w;}
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i) cin>>p[i].u>>p[i].v>>p[i].w;
sort(p+1,p+m+1,cmp);
for(int i=1,fx,fy;i<=m;++i)
{
fx=find(p[i].u),fy=find(p[i].v);
if(fx==fy) continue;
fa[fx]=fy,++tot;
maxx=max(maxx,p[i].w);//喵
if(tot==n-1) break;
}
cout<<maxx<<"\n";
return 0;
}
P2330 [SCOI2005] 繁忙的都市
上一道题的多倍经验。
P1111 修复公路
上一道题的多倍经验。
P1551 亲戚
板子题，和板子只差了个输出。
P3535 [POI2012] TOU-Tour de Byteotia
贪心题，但是证明可能会有点绕（oi是这样的）。一张无向图上，\(n\) 个点 \(m\) 条边，询问至少需要删除几条边才能使得前 \(k\) 个点不在环上，题面要求输出删除的边，但是数据没要求（现在不知道力）。
首先对于一条边 \(u \to v\)，如果 \(u>k\) 且 \(v>k\) 的话它是影响不到前 \(k\) 个点的，所以这些边一定不被删，并使用并查集将这些边全部加进去。再枚举其他的边，如果边 \(u \to v\)，两点 \(u,v\) 的祖先相同，那么现在已经加入的边就已经使得这两个点连通了，再加上这条边就必成环，所以这条边就需要删，否则这条边不被删，加入并查集中。
代码：
const int M=1e6+5;
int n,m,k,ans;
int u[M],v[M],fa[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
ans=m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i];
if(u[i]>k&&v[i]>k)
{
int x=find(u[i]),y=find(v[i]);
ans--;//这种边不会被删
if(x==y) continue;
fa[x]=y;
}
}
for(int i=1;i<=m;i++)
{
if(!(u[i]>k&&v[i]>k))
{
int x=find(u[i]),y=find(v[i]);
if(x==y) continue;
fa[x]=y,ans--;//这种加入进去两边不成环的也不会被删
}
}
cout<<ans<<"\n";
return 0;
}
P1955 [NOI2015] 程序自动分析
给定 \(k\) 个约束关系形如 \(i,j,e\)，若 \(e=1\) 表示 \(x_i=x_j\)，否则表示 \(x_i \neq x_j\)，询问各个约束条件是否存在矛盾。
有等于和不等于的关系，那么我们可以考虑等于就相当于并查集中的合并操作，不等于就相当于并查集中的祖先不一样。那么我们先将所有等于的操作处理完，将满足等于的各个变量合并在一起，然后对于每个不等的约束判断 \(i,j\) 的祖先相不相同，如果不相同就出现了矛盾。
注意：本题的 \(i,j\) 相当大，需要离散化（这是一个很常用的操作，是对于只关注数的相对大小而不在意数的绝对大小时，数的绝对大小较大，想将数约束在较小范围的操作），主要有两种做法，一种是二分，还有一种是 '''map'''，进行映射（建议参考网上资料）。
代码（有点古老了）：
const int M=200005;
int T,n;
int a[M],b[M],c[M],fa[M],l[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
cin>>T;
while(T--)
{
int tot=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i]>>c[i];
l[++tot]=a[i],l[++tot]=b[i];
}
sort(l+1,l+tot+1);
int len=unique(l+1,l+tot+1)-l-1;
int maxx=0;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(l+1,l+len+1,a[i])-l;
b[i]=lower_bound(l+1,l+len+1,b[i])-l;//二分离散化的方法
maxx=max(maxx,max(a[i],b[i]));
}
for(int i=1;i<=maxx;i++) fa[i]=i;
for(int i=1;i<=n;i++)
{
if(c[i])//将所有相等的操作合并
{
int x=find(a[i]),y=find(b[i]);
if(x!=y) fa[x]=y;
}
}
int flag=0;
for(int i=1;i<=n;i++)
{
if(!c[i])//将所有不等的操作进行判断
{
int x=find(a[i]),y=find(b[i]);
if(x==y)
{
flag=1;
break;
}
}
}
if(flag) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
P1892 [BOI2003] 团伙
拓展域并查集的板子题（严格上来说拓展域能做的带权并查集都可以做，这里先介绍拓展域并查集）。
拓展域并查集主要适用范围是对于点与点之间可能存在多种状态（一般较小，多数时候为 2），例如这题就存在两种状态：朋友与敌人。
那么这时候对于每一个点还是朴素的进行并查集就有点力不从心了，所以对于这道题，我们可以对于一个点建一个反点，于是对于每个人就有两个点： \(i\) 表示正点，与 \(i\) 的朋友们相连，\(i+n\) 表示反点，与 \(i\) 的敌人们相连，当然初始化都是初始化的 \(fa_i=i\) 。这个时候题目中的两个操作就简单了：
对于是朋友的两个人：将 \(x\) 与 \(y\) 合并（为何不合并 \(x+n\) 与 \(y+n\)，因为题目中没有说敌人的朋友是敌人，那就不管了）。
对于是敌人的两个人：将 \(x\) 与 \(y+n\) 合并，将 \(x+n\) 与 \(y\) 合并。
其实发现，\(i+1 \sim 2n\) 充当了一个中转点的角色，负责将自己的敌人与自己的另外一堆敌人相连（至于点与点还存在更多种状态，也是形如这样做）。
最后询问最多的团体数，那就是 \(fa_i=i\) 的节点数，当然只统计 \(1 \sim n\) 的点。
代码：
const int M=1e4+5;
int n,q,ans;
int fa[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=(n<<1);i++) fa[i]=i;//初始化2*n个点，空间也要开2倍
char opt;int x,y;
while(q--)
{
cin>>opt>>x>>y;
if(opt=='F') fa[find(x)]=find(y);
else
{
fa[find(x+n)]=find(y);
fa[find(y+n)]=find(x);
}
}
for(int i=1;i<=n;i++)
{
if(find(i)==i) ++ans;
}
cout<<ans<<"\n";
return 0;
}
P1525 [NOIP2010 提高组] 关押罪犯
和上一道题很像，但是转化的过程难想多了。由于现在我们有 2 个监狱，我们没法具体的操控某个人前往哪个监狱，但是我们可以判断两个人是否在同一个监狱啊！
所以某两个点之间就存在两种情况：在同一个监狱和不在同一个监狱。考虑逻辑 \(a\) 与 \(b\) 在同一个监狱，\(b\) 和 \(c\) 在同一个监狱，那么 \(a\) 与 \(c\) 在同一个监狱；\(a\) 与 \(b\) 不在同一个监狱，\(a\) 与 \(c\) 不在同一个监狱，那么 \(b\) 和 \(c\) 就一定在同一个监狱了，这下就和上一题的操作一样了，还是采用拓展域并查集进行求解。
但本题中是想让爆发冲突的影响力最小，那么对于影响力大的两人肯定选择先行放到两个不同的监狱，直到对于其中一组会爆发冲突的两人已经被放在同一个监狱了，那么这时候爆发的影响力一定就是最小的。（因为两人都为了避免爆发影响力更大的事件而不得不被分配到了这一个监狱）。
对于还没有到不得不在在一起的两人 \(x,y\)，在并查集里加入这两人不在一个监狱的指令，合并 \(x,y+n\) 与 \(x+n,y\)。
代码：
const int M=1e5+5;
int n,m;
int fa[M];
struct N{
int a,b,x;
};N p[M];
inline bool cmp(N a,N b)
{
return a.x>b.x;
}//按影响力从大到小排序
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
inline void merge(int a,int b)
{
int x=find(a),y=find(b);
fa[x]=y;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>p[i].a>>p[i].b>>p[i].x;
for(int i=1;i<=2*n;i++) fa[i]=i;//初始化2倍
sort(p+1,p+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=find(p[i].a),y=find(p[i].b);
if(x==y)//如果此时两人已经在同一个监狱了
{
cout<<p[i].x<<"\n";
return 0;
}
merge(p[i].a+n,p[i].b),merge(p[i].b+n,p[i].a);//否则这两个人不在同一个监狱
}
cout<<"0\n";
return 0;
}
P8710 [蓝桥杯 2020 省 AB1] 网络分析
\(n\)个节点，\(m\)个操作，共有两种操作：一种操作是表示将节点 \(a\) 和节点 \(b\) 通过连接起来，还有一种表示在节点 \(p\) 上发送一条大小为 \(t\) 的信息，此时所有与 \(p\) 相连的点都会收到这条信息，询问最后每个点接收到的信息大小总量。
考虑朴素的做法，对于操作 1 直接使用并查集合并即可，对于操作 2 ，暴力遍历一遍每个点，将所有与 \(p\) 祖先相同的点（同一集合）的权值加上 \(t\) 。
这样做时间复杂度肯定会爆，考虑优化，我们可以将权值 \(t\) 加在 \(p\) 的根上面，但是存在合并操作，每个点的根在变化。那么我们就在变化的时候——合并操作的时候将每个根节点上记录的权值下传即可，这样时间复杂度是 \(O(n^2)\) 级别的，因为最多只会合并 \(n\) 次。
代码：
const int M=1e5+5;
int n,q;
int fa[M],res[M],ans[M],siz[M];//ans记录的是第i个点的权值，res记录的是做为根当前还没有下传的权值
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1;
int opt,x,y,fx,fy;
while(q--)
{
cin>>opt>>x>>y;
if(opt==1)
{
fx=find(x),fy=find(y);
if(fx==fy) continue;
for(int i=1;i<=n;i++) ans[i]+=res[find(i)];//每次合并就把res下传下去
for(int i=1;i<=n;i++) res[i]=0;//清空res
if(siz[fx]>siz[fy]) swap(fx,fy);
fa[fx]=fy,siz[fy]+=siz[fx];
}
else res[find(x)]+=y;//x的根+y的待下传权值
}
for(int i=1;i<=n;++i) cout<<ans[i]+res[find(i)]<<" ";//最后答案是根节点上没有下传的权值+本点的权值
return 0;
}
P5836 [USACO19DEC] Milk Visits S
有点巧妙啊，这题做法其实挺多的，这里就介绍并查集的做法了。对于一条边相连的两个点，如果两端连接的颜色相同，那么就把它们合并。
那么判断的时候怎么判断？如果对于给定的图是一棵树，如果给定的路径 \(u \to v\) 上的点奶牛种类全部相同的话，那么 \(u,v\) 一定在同一个集合内，这个时候判断这个点代表的奶牛是否为客人喜欢的。那么如果这两点不在同一个集合内，就说明路径上有多种奶牛，那么一定能满足客人的需求，
代码：
const int M=1e5+5;
int n,m;
int fa[M];
char s[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i],fa[i]=i;
int a,b,x,y;char opt;
for(int i=1,a,b,x,y;i<n;i++)
{
cin>>a>>b;
if(s[a]==s[b])//如果两点相同就合并
{
x=find(a),y=find(b);
fa[x]=y;
}
}
for(int i=1;i<=n;i++) find(i);
for(int i=1;i<=m;i++)
{
cin>>a>>b>>opt;
if(fa[a]==fa[b]&&s[fa[a]]!=opt) cout<<"0";//如果路径两端是在一个集合内（路径上全是一种奶牛&不和客人口味）
else cout<<"1";
}
return 0;
}
P5937 [CEOI1999] Parity Game
转化一下就是拓展域并查集，考虑对于每一个点 \(i\) 设其表示的是前 \(i\) 个数总共有奇数个 1 还是偶数个 1。
那么对于它的操作就比较显然了（先不考虑与前面是否矛盾），如果给定的区间 \(x \sim y\) 存在偶数个 1，那么 \(x\) 与 \(y\) 的奇偶性相同，反之存在奇数个 1 ，那么 \(x\) 与 \(y\) 的奇偶性不同。
于是用 \(i\) 表示与 \(i\) 奇偶性相同的点，\(i+n\) 表示与 \(i\) 奇偶性不同的点。但是这题和上面的板子题有一点不一样的是，与 \(z\) 奇偶性不相同的点 \(x\)，与 \(x\) 奇偶性相同的点 \(y\) ，\(z\) 一定也与 \(y\) 奇偶性不同（相当于给定了敌人的朋友也是敌人），所以在给定 \(x\) 与 \(y\) 奇偶性相同的条件时，还需要连接 \(x+n\) 与 \(y+n\) （成为朋友了之后一起对付彼此的敌人）。
那么判断矛盾也比较简单，如果 \(x\) 和 \(y\) 奇偶性相同，结果 \(x\) 和 \(y+n\) 在一起或者 \(y+n\) 与 \(x\) 在一起，另一种操作同理。
给定的下标大小过大，需要使用离散化处理（毕竟这题不在意序列下标的绝对大小）。
代码：
const int M=1e5+5;
int n,m,cnt=0;
int fa[M],c[M];
struct N{
int a,b,opt;
};N p[M];
inline int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
inline void merge(int a,int b)
{
int x=find(a),y=find(b);
fa[x]=y;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;char opt[5];
for(int i=1;i<=m;i++)
{
cin>>p[i].a>>p[i].b>>opt;
p[i].a--;
if(opt[0]=='e') p[i].opt=0;
else p[i].opt=1;
c[++cnt]=p[i].a,c[++cnt]=p[i].b;
}
sort(c+1,c+cnt+1);
int len=unique(c+1,c+cnt+1)-c-1;
for(int i=1;i<=m;i++)
{
p[i].a=lower_bound(c+1,c+len+1,p[i].a)-c;
p[i].b=lower_bound(c+1,c+len+1,p[i].b)-c;
}//以上是离散化
for(int i=1;i<=2*m;i++) fa[i]=i;//预处理
for(int i=1;i<=m;i++)
{
if(!p[i].opt)//偶数个 奇偶相同
{
if(find(p[i].a)==find(p[i].b+m))
{
cout<<i-1<<"\n";return 0;
}
merge(p[i].a,p[i].b),merge(p[i].a+m,p[i].b+m);//a&b a+n&b+n
}
else//奇数个 奇偶相反
{
if(find(p[i].a)==find(p[i].b))
{
cout<<i-1<<"\n";return 0;
}
merge(p[i].a+m,p[i].b),merge(p[i].b+m,p[i].a);//a+n&b a&b+n
}
}
cout<<m<<"\n";
return 0;
}
P6121 [USACO16OPEN] Closing the Farm G
第三题的加强版，但是并查集都过得去，双倍经验了
咕咕咕，明日再战。