网站添加可信任站点怎么做,微营销是什么意思,有哪些在线做图的网站,做网站能带来什么问题P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 写法一#xff1a;Tarjan
思路#xff1a;先运用Tarjan算法得到每个连通块中最大的编号#xff0c;然后对每个连通块进行缩点重新建图#xff0c;进行dfs#xff0c;得到缩点后的连通块能够达到的最大编号。
Code: conste… P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 写法一Tarjan
思路先运用Tarjan算法得到每个连通块中最大的编号然后对每个连通块进行缩点重新建图进行dfs得到缩点后的连通块能够达到的最大编号。
Code: constexpr int N1e55,mod1e97;int a[N],dfn[N],stk[N],low[N],top,scc[N],cnt,tot;
int n,m,instack[N],ma[N],sz[N];
bool st[N];
int x[N],y[N];
vectorint e[N],g[N];void Tarjan(int u)
{stk[top]u,instack[u]1;low[u]dfn[u]tot;for(auto t:e[u]){if(!dfn[t]){Tarjan(t);low[u]min(low[u],low[t]);}else if(instack[t]) low[u]min(low[u],dfn[t]);}if(low[u]dfn[u]){cnt; int y;//cout____cnt uendl;do{ystk[top--]; instack[y]0;scc[y]cnt;// cout____cnt yendl;ma[cnt]max(ma[cnt],y);}while(u!y);}
}void dfs(int u)
{if(a[u]) return ;a[u]ma[u];// coutu a[u] g[u].size()endl;for(auto t:g[u]){if(!a[t]){dfs(t);}a[u]max(a[u],a[t]);// coutu t a[u]endl;}
}
void solve()
{cinnm;for(int i0;im;i){cinx[i]y[i];e[x[i]].push_back(y[i]);}for(int i1;in;i)if(!dfn[i])Tarjan(i);for(int i0;im;i){if(scc[x[i]]scc[y[i]]) continue;g[scc[x[i]]].push_back(scc[y[i]]);}for(int i1;icnt;i){if(!a[i]) dfs(i);}for(int i1;in;i)couta[scc[i]] ;
}写法二反向建图
既然要计算每个点能走到的最大编号我们可以直接从大编号 开始搜索与它关联的路径该路径上的点均为大编号。
Code:
constexpr int N1e55,mod1e97;int a[N],n,m;
vectorint e[N];void dfs(int u,int i)
{if(a[u]) return ;a[u]i;for(auto t:e[u]){if(!a[t]){dfs(t,i);}}}
void solve()
{cinnm;for(int i1;im;i){int a,b;cinab;e[b].push_back(a);}for(int in;i;i--)if(!a[i]) dfs(i,i);for(int i1;in;i) couta[i] ;
}
