首页 > 代码库 > 强联通块tarjan算法
强联通块tarjan算法
http://poj.org/problem?id=1236
第一问：需要几个学校存在软件，才能通过传递，使得所有的学校都有软件
用tarjan算法求出强联通分量后，将每个联通分量缩成一个点，那么问题1的答案就是入度为0的点的个数
为什么？入度为0的点，肯定不能通过其他学校传送软件给他，所以他必须存在一份软件
第二问：需要加几条边，才能使得图强联通
缩点后，a为所有入度为0的点的个数，b为所有出度为0的点的个数，那么答案就是max(a,b)
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 #include <stack> 5 using namespace std; 6 const int N = 100 + 10; 7 vector<int> G[N]; 8 stack<int> st; 9 bool vis[N];10 int sccno[N],pre[N],lowlink[N],in[N],out[N],dfs_clock,scc_cnt;11 int min(const int &a, const int &b)12 {13 return a < b ? a : b;14 }15 void tarjan(int u)16 {17 pre[u] = lowlink[u] = ++dfs_clock;18 st.push(u);19 for(int i=0; i<G[u].size(); ++i)20 {21 int v = G[u][i];22 if(!pre[v])23 {24 tarjan(v);25 lowlink[u] = min(lowlink[u],lowlink[v]);26 }27 else if(!sccno[v])28 lowlink[u] = min(lowlink[u],pre[v]);29 }30 if(lowlink[u]==pre[u])31 {32 scc_cnt++;33 for(;;)34 {35 int x = st.top();st.pop();36 sccno[x] = scc_cnt;37 if(x==u) break;38 }39 }40 }41 void find_scc(int n)42 {43 for(int i=1; i<=n; ++i)44 if(!pre[i])45 tarjan(i);46 }47 int main()48 {49 int n,i,a,b;50 scanf("%d",&n);51 for(a=1; a<=n; ++a)52 {53 while(scanf("%d",&b),b)54 {55 G[a].push_back(b);56 vis[b] = true;57 } 58 }59 find_scc(n);60 for(i=1; i<=scc_cnt; ++i) in[i] = out[i] = 1;61 for(int u=1; u<=n; ++u)62 for(i=0; i<G[u].size();++i)63 {64 int v = G[u][i];65 if(sccno[u] != sccno[v]) in[sccno[v]] = out[sccno[u]] = 0;66 }67 a = b = 0;68 for(i=1; i<=scc_cnt; ++i)69 {70 if(in[i]) a++;71 if(out[i]) b++;72 } 73 int ans = a > b ? a : b;74 if(scc_cnt == 1) ans = 0;75 printf("%d\n%d\n",a,ans);76 return 0;77 }
强联通块tarjan算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。