中国建设银行网站个人客户首页,天山网官网,wordpress 添加编辑,信息技术 网站建设教案正题
题目链接:https://www.luogu.com.cn/problem/P2272 题目大意
半连通图定义为任意两个点(u,v)(u,v)(u,v)满足uuu可以到vvv或vvv可以到uuu的有向图。
现在给出一张图#xff0c;求最大半连通子图与其数量。 解题思路
显然一个强连通一定是一个半连通#xff0c;所以我…正题
题目链接:https://www.luogu.com.cn/problem/P2272 题目大意
半连通图定义为任意两个点(u,v)(u,v)(u,v)满足uuu可以到vvv或vvv可以到uuu的有向图。
现在给出一张图求最大半连通子图与其数量。 解题思路
显然一个强连通一定是一个半连通所以我们可以先tarjantarjantarjan缩点。
可以发现半连通一定是缩完点之后的DAGDAGDAG上的一条链所以我们可以用dpdpdp解决。
需要注意的是如果两条边连通两个相同缩完后的点这些重边需要去掉否则会对统计答案造成影响。
时间复杂度O(mlogmn)O(m\log mn)O(mlogmn)改用hashhashhash去重可以去掉那个logm\log mlogm的复杂度 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
#includequeue
using namespace std;
const int N1e510;
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];
stackint s;queueint q;
void addl(int x,int y){a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;return;
}
void tarjan(int x){dfn[x]low[x]cnt;ins[x]1;s.push(x);for(int ils[x];i;ia[i].next){int ya[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 i1;inum;i){if(!in[i])q.push(i);f[i]siz[i];g[i]1;ansmax(ans,f[i]);}while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[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;ansmax(ans,f[y]);if(!in[y])q.push(y);}}return;
}
int main()
{scanf(%d%d%d,n,m,p);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(y,x);}for(int i1;in;i)if(!dfn[i])tarjan(i);sort(a1,a1tot,cmp);int pttot,lx0,ly0;tot0;memset(ls,0,sizeof(ls));for(int i1;ipt;i){int xa[i].from,ya[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]];lxx;lyy;}topsort();printf(%d\n,ans);int sum0;for(int i1;in;i)if(f[i]ans)(sumg[i])%p;printf(%d\n,sum);return 0;
}
