首页 > 代码库 > UVALive 4287 SCC-Tarjan 加边变成强连通分量
UVALive 4287 SCC-Tarjan 加边变成强连通分量
还是强连通分量的题目,但是这个题目不同的在于,问你最少要添加多少条有向边,使得整个图变成一个强连通分量
然后结论是,找到那些入度为0的点的数目 和 出度为0的点的数目,取其最大值即可,怎么证明嘛。。。我也不好怎么证,不过细细一琢磨发现就是这样,改天找聪哥一起探讨下怎么证明
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <stack>using namespace std;const int N=20010;int pre[N],lowlink[N],sccno[N];vector<int>G[N],G2[N];stack<int> sta;int n,m,vis[N],scc_cnt,dfs_clk;int ind[N],outd[N];void init(){ for (int i=0;i<=n;i++){ pre[i]=0; lowlink[i]=0; sccno[i]=0; G[i].clear(); G2[i].clear(); vis[i]=0; scc_cnt=dfs_clk=0; ind[i]=outd[i]=0; }}void dfs(int u){ pre[u]=lowlink[u]=++dfs_clk; sta.push(u); for (int i=0;i<G[u].size();i++){ int v=G[u][i]; if (!pre[v]){ dfs(v); lowlink[u]=min(lowlink[u],lowlink[v]); } else if (!sccno[v]){ lowlink[u]=min(lowlink[u],pre[v]); } } if (lowlink[u]==pre[u]){ scc_cnt++; for (;;){ int x=sta.top();sta.pop(); sccno[x]=scc_cnt; if (x==u) break; } }}void tarjan(){ for (int i=1;i<=n;i++){ if (!pre[i]) dfs(i); } for (int i=1;i<=n;i++){ int u=sccno[i]; for (int j=0;j<G[i].size();j++){ int v=G[i][j]; v=sccno[v]; if (u!=v){ G2[u].push_back(v); ind[v]++; outd[u]++; } } }}int main(){ int t; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); init(); int a,b; while (m--){ scanf("%d%d",&a,&b); G[a].push_back(b); } tarjan(); if (scc_cnt==1){ puts("0"); continue; } int ans1=0,ans2=0; for (int i=1;i<=scc_cnt;i++){ if (ind[i]==0) ans1++; if (outd[i]==0) ans2++; } printf("%d\n",max(ans1,ans2)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。