正題

題目鏈接:https://www.luogu.com.cn/problem/P7323

---

題目大意

給出$n$個點的一張有向圖。每個邊$(u,v,w)$表示$u?>v$有一個類型$w$的左括號邊，$v?>u$有一個類型$w$的右括號邊。

求圖中有多少點對滿足它們之間有一條合法的括號序列路徑

$1\le n\le 3\times 10^5,1\le m\le 6\times 10^5,1\le k\le n$

---

解題思路

一個顯然的結論是如果兩個點之間有合法路徑那么連一條邊的話，那么最后出來的是一個團。

因為$f(u,v)=1?f(v,u)=1$（路徑翻轉），$f(u,v)=f(v,z)=1?f(u,z)=1$（路徑拼接）。

考慮怎么求出這些團。假設我們現在有一個團$x$，它連接向團外有兩條類型一樣的邊，那么就代表我們可以把這兩條邊連接的節點（或者團）合并入這個團中。

然后合并的時候我們因為又要處理類型一樣的邊，所以我們用啟發式合并枚舉小的那個暴力丟進大的里面就好了。

時間復雜度$O(n{\log }^{2}n)$，用線段樹合并可以做到$O(n\log n)$（也許？

---

code

#include<cstdio> #include<cstring> #include<queue> #include<map> #define mp(x,y) make_pair(x,y) using namespace std; const int N=3e5+10; int n,m,k,fa[N],cnt[N]; long long ans; queue<pair<int,int> >q; map<int,int> G[N]; int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} map<int,int>::iterator it; int main() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);swap(x,y);if(G[x][w])q.push(mp(G[x][w],y));else G[x][w]=y;}for(int i=1;i<=n;i++)fa[i]=i;while(!q.empty()){int x=q.front().first,y=q.front().second;x=find(x);y=find(y);q.pop();if(x==y)continue;if(G[x].size()<G[y].size())swap(x,y);for(it=G[y].begin();it!=G[y].end();it++){int w=it->first,z=it->second;if(G[x][w])q.push(mp(G[x][w],z));else G[x][w]=z;}fa[y]=x;}for(int i=1;i<=n;i++)cnt[find(i)]++;for(int i=1;i<=n;i++)ans+=1ll*cnt[i]*(cnt[i]-1)/2ll;printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的P7323-[WC2021]括号路径【并查集,启发式合并】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。