首页 / 算法 / 算法笔记--强连通分量分解
算法笔记--强连通分量分解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记--强连通分量分解,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1894字,纯文字阅读大概需要3分钟。
内容图文
![算法笔记--强连通分量分解](/upload/InfoBanner/zyjiaocheng/1118/9e0af0a0e28f4c748596605b8b1147fa.jpg)
Kosaraju算法
详见《挑战程序设计竞赛》p320
模板:
const int N=1e5+5; int n,m; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++) if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++) if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=1;i<=n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; }
代码:
![技术分享](/img/jia.gif)
![技术分享](/img/jian.gif)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> usingnamespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) constint N=1e5+5; int n,m; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N]; void add_edge(int u,int v) { g[u].pb(v); rg[v].pb(u); } void dfs(int u) { vis[u]=true; for(int i=0;i<g[u].size();i++) if(!vis[g[u][i]])dfs(g[u][i]); vs.pb(u); } void rdfs(int u,int k) { vis[u]=true; cmp[u]=k; for(int i=0;i<rg[u].size();i++) if(!vis[rg[u][i]])rdfs(rg[u][i],k); } int scc() { mem(vis,false); vs.clear(); for(int i=1;i<=n;i++)if(!vis[i])dfs(i); mem(vis,false); int k=0; for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++); return k; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int u,v; for(int i=0;i<m;i++)cin>>u>>v,add_edge(u,v); int t=scc(); int ans=0; for(int i=1;i<=n;i++)if(cmp[i]==t-1)ans++,u=i; mem(vis,false); rdfs(u,0); for(int i=1;i<=n;i++)if(!vis[i])ans=0; cout<<ans<<endl; return0; }
例题2:
原文:http://www.cnblogs.com/widsom/p/7637280.html
内容总结
以上是互联网集市为您收集整理的算法笔记--强连通分量分解全部内容,希望文章能够帮你解决算法笔记--强连通分量分解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。