題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)由 n 個(gè)點(diǎn)和 m 條邊組成的無向圖，每個(gè)點(diǎn)初始時(shí)都有顏色 i ，i ∈ [ 0 , n - 1 ] ，接下來有 q 次操作，每次操作會(huì)給出一種顏色 x ，分兩種情況討論：

如果顏色為 x 的點(diǎn)不存在，則跳過此次操作

如果顏色為 x 的點(diǎn)存在，則將顏色為 x 的點(diǎn)的相鄰的所有顏色塊，都染成 x 的顏色

問最后每個(gè)點(diǎn)的顏色是什么

題目分析：合并問題不難想到并查集，對于每個(gè)點(diǎn)的顏色可以用并查集來維護(hù)，不過如果暴力更新的話肯定會(huì) T ，有一個(gè)比較顯然且比較重要的結(jié)論就是，每個(gè)點(diǎn)至多被遍歷一次，因?yàn)槿绻?dāng)某個(gè)點(diǎn)被遍歷過一次后，那么其相鄰的所有點(diǎn)肯定和當(dāng)前的點(diǎn)都變?yōu)橥粋€(gè)顏色了，接下來無論如何操作，再遍歷這個(gè)點(diǎn)肯定是沒有任何進(jìn)展的了，所以基于這個(gè)性質(zhì)，我們可以用鏈表配合并查集實(shí)現(xiàn)模擬

首先并查集的 f 數(shù)組配合 find 函數(shù)用來維護(hù)每個(gè)點(diǎn)被染成的顏色，初始化為每個(gè)點(diǎn)本身，其次每個(gè)顏色都建立一個(gè)鏈表，用來儲(chǔ)存當(dāng)前顏色下有多少個(gè)點(diǎn)被染成了相同的顏色

對于每一個(gè)詢問的顏色 x ，如果不存在的話，直接跳過即可，如果存在的話，可以遍歷一遍相應(yīng)的鏈表進(jìn)行擴(kuò)展，根據(jù)上面的性質(zhì)可知，遍歷過的元素直接刪除掉即可，對于新加入的元素，可以利用鏈表的 splice 方法，這個(gè)方法可以 O( 1 ) 合并兩個(gè)鏈表，如此一來，整體的時(shí)間復(fù)雜度也只是 O( n * a + m?)，a 是并查集的時(shí)間開銷

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<list> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=8e5+100;list<int>li[N];vector<int>node[N];int f[N];void init(int n) {for(int i=0;i<n;i++){f[i]=i;li[i].clear();li[i].push_back(i);node[i].clear();} }int find(int x) {return x==f[x]?x:f[x]=find(f[x]); }void merge(int x,int y)//xx合并到y(tǒng)y {int xx=find(x);int yy=find(y);if(xx!=yy){f[xx]=yy;li[yy].splice(li[yy].end(),li[xx]);} }void update(int x) {if(x!=find(x))return;int sz=li[x].size();while(sz--){int u=li[x].front();li[x].pop_front();for(auto v:node[u])merge(v,u);} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);init(n);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}int q;scanf("%d",&q);while(q--){int x;scanf("%d",&x);update(x);}for(int i=0;i<n;i++)printf("%d ",find(i));puts("");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校3 - Operating on a Graph(并查集+链表合并)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。