正題

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

---

題目大意

半連通圖定義為任意兩個點$(u,v)$滿足$u$可以到$v$或$v$可以到$u$的有向圖。

現在給出一張圖，求最大半連通子圖與其數量。

---

解題思路

顯然一個強連通一定是一個半連通，所以我們可以先$tarjan$縮點。

可以發現半連通一定是縮完點之后的$DAG$上的一條鏈，所以我們可以用$dp$解決。

需要注意的是如果兩條邊連通兩個相同縮完后的點，這些重邊需要去掉，否則會對統計答案造成影響。

時間復雜度$O(m\log m+n)$，改用$hash$去重可以去掉那個$\log m$的復雜度

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> using namespace std; const int N=1e5+10; struct node{int to,from,next; }a[N*10]; int n,p,m,tot,cnt,num,ls[N]; int dfn[N],low[N],col[N],siz[N]; int f[N],g[N],in[N],ans;bool ins[N]; stack<int> s;queue<int> q; void addl(int x,int y){a[++tot].to=y;a[tot].from=x;a[tot].next=ls[x];ls[x]=tot;return; } void tarjan(int x){dfn[x]=low[x]=++cnt;ins[x]=1;s.push(x);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){++num;while(s.top()!=x){ins[s.top()]=0;col[s.top()]=num;siz[num]++;s.pop();}ins[s.top()]=0;col[s.top()]=num;siz[num]++;s.pop();}return; } bool cmp(node x,node y) {return (col[x.from]==col[y.from])?col[x.to]<col[y.to]:col[x.from]<col[y.from];} void topsort(){for(int i=1;i<=num;i++){if(!in[i])q.push(i);f[i]=siz[i];g[i]=1;ans=max(ans,f[i]);}while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;in[y]--;if(f[x]+siz[y]>f[y])f[y]=f[x]+siz[y],g[y]=g[x];else if(f[x]+siz[y]==f[y])g[y]=(g[y]+g[x])%p;ans=max(ans,f[y]);if(!in[y])q.push(y);}}return; } int main() {scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(y,x);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);sort(a+1,a+1+tot,cmp);int pt=tot,lx=0,ly=0;tot=0;memset(ls,0,sizeof(ls));for(int i=1;i<=pt;i++){int x=a[i].from,y=a[i].to;if(col[x]==col[lx]&&col[y]==col[ly])continue;if(col[x]!=col[y])addl(col[y],col[x]),in[col[x]]++;lx=x;ly=y;}topsort();printf("%d\n",ans);int sum=0;for(int i=1;i<=n;i++)if(f[i]==ans)(sum+=g[i])%=p;printf("%d\n",sum);return 0; }

總結

以上是生活随笔為你收集整理的P2272-[ZJOI2007]最大半连通子图【tarjan,缩点】的全部內容，希望文章能夠幫你解決所遇到的問題。

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