【ybt】【图论强连通课过例3】最大半连通子图

本文主要是介绍【ybt】【图论强连通课过例3】最大半连通子图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最大半连通子图

题目链接：最大半连通子图

题目描述

在这里插入图片描述

解题思路

我们可以发现，任何一个半联通子图在缩点后都是一条链，所以我们可以先用 $T a r j a n$ 缩点，然后用 $d f s$ 找出最大的数量，再跑一边找一共有多少个。

code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;long long ans;int maxn;
int n,m,mod;
int ttt,tm,tt;
int v[100010];
int az[100010];
int dis[100010];
int num[100010];
int dfn[100010];
int low[100010];
int rem[100010];
int dui[100010],top;
int hd[100010],tot;
int hd1[100010],tot1;struct abc{int to,nxt;
}b[1000010],b1[1000010];struct abcd{int x,y;
}t[1000010];bool cmp(abcd p,abcd q)
{if(p.x!=q.x)return p.x<q.x;return p.y<q.y;
}void add(int x,int y)
{b[++tot]=(abc){y,hd[x]};hd[x]=tot;
}void add1(int x,int y)
{b1[++tot1]=(abc){y,hd1[x]};hd1[x]=tot1;
}int dfs(int x)
{if(dis[x])return dis[x];int s=num[x];for(int i=hd1[x];i;i=b1[i].nxt){int y=b1[i].to;dis[y]=dfs(y);s=max(s,num[x]+dis[y]);}return s;
}int getnum(int x,int f)
{if(!f)return 1;if(rem[x]!=-1)return rem[x];rem[x]=0;for(int i=hd1[x];i;i=b1[i].nxt){int y=b1[i].to;if(dis[y]+num[x]==dis[x])rem[x]=(rem[x]+getnum(y,f-num[y]))%mod;}return rem[x];
}void tarjan(int x)
{dfn[x]=low[x]=++tm;dui[++top]=x;az[x]=1;for(int i=hd[x];i;i=b[i].nxt){int y=b[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(az[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){v[x]=++tt;while(dui[top]!=x){v[dui[top]]=tt;az[dui[top]]=0;num[tt]++;top--;}top--;az[x]=0;num[tt]++;}
}int main()
{cin>>n>>m>>mod;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)for(int j=hd[i];j;j=b[j].nxt){int y=b[j].to;if(v[i]!=v[y])t[++ttt]=(abcd){v[i],v[y]};}sort(t+1,t+ttt+1,cmp);for(int i=1;i<=ttt;i++)if(!(t[i].x==t[i-1].x&&t[i].y==t[i-1].y))add1(t[i].x,t[i].y);for(int i=1;i<=tt;i++)if(!dis[i]){dis[i]=dfs(i);maxn=max(maxn,dis[i]);}cout<<maxn<<endl;memset(rem,-1,sizeof(rem));for(int i=1;i<=tt;i++)if(dis[i]==maxn){rem[i]=getnum(i,maxn-num[i]);ans=(ans+(1ll*rem[i]))%mod;}cout<<ans<<endl;
}