2020牛客暑期多校训练营（第三场） G-Operating on a Graph
Operating on a Graph
https://ac.nowcoder.com/acm/contest/5668/G
题目大意
其实这道题原题直译着实难理解，但是可以用一些形象的方式来理解：
给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的颜色全都变成 oi (若已没有颜色oi 已被侵略，则该次操作无效)，求最终每个点的颜色。（自官方题解PPT）
解题思路
对于颜色，在这里可以用并查集维护，根结点表示颜色。
操作一种颜色时，与其相连的所有点颜色都会改变，所以对于每个点至多会有一次侵略操作。
使用一组vector，记录第i种颜色所相邻的点，每次操作时把x颜色相邻的每个点（将y分别赋值为a[x]中的点）所相邻的点集（a[y]中的点），转为x相邻的点集，y所在集合的颜色变为x。
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int> a[800010],b;
int f[800010];
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main()
{
int t,n,m,q,x,y,z,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)
f[i]=i,a[i].clear();
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&x);
if(f[x]!=x) continue;
b=a[x];a[x].clear();
for(i=0;i<b.size();i++)
{
y=find(b[i]);
if(y!=x)
{
f[y]=x;
if(a[x].size()<a[y].size()) swap(a[x],a[y]);
for(j=0;j<a[y].size();j++)
a[x].push_back(a[y][j]);
}
}
}
for(i=0;i<n;i++)
printf("%d ",find(i));
printf("\n");
}
return 0;
}
2020牛客暑期多校训练营 文章被收录于专栏
只是题解，可参考，可学习，可点赞:)
美的集团公司福利 815人发布
查看15道真题和解析