首页 > 代码库 > POJ 1236 Network of School
POJ 1236 Network of School
http://poj.org/problem?id=1236
题意：
给出一个图，至少要选多少个点才能遍历全图和至少需要添加多少边使得整个图是强连通。
思路：
强连通计算连通分量后缩点，计算入度为0的点和出度为0的点。
第一个答案就是出度为0的点，第二个就是max（出度，入度）。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=100+5;13 14 int n;15 16 vector<int> G[maxn];17 int in[maxn],out[maxn];18 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;19 stack<int> S;20 21 void dfs(int u)22 {23 pre[u]=lowlink[u]=++dfs_clock;24 S.push(u);25 for(int i=0;i<G[u].size();i++)26 {27 int v=G[u][i];28 if(!pre[v])29 {30 dfs(v);31 lowlink[u]=min(lowlink[u],lowlink[v]);32 }33 else if(!sccno[v])34 {35 lowlink[u]=min(lowlink[u],pre[v]);36 }37 }38 if(lowlink[u]==pre[u])39 {40 scc_cnt++;41 for(;;)42 {43 int x=S.top(); S.pop();44 sccno[x]=scc_cnt;45 if(x==u) break;46 }47 }48 }49 50 void find_scc()51 {52 dfs_clock=scc_cnt=0;53 memset(sccno,0,sizeof(sccno));54 memset(pre,0,sizeof(pre));55 for(int i=1;i<=n;i++)56 if(!pre[i]) dfs(i);57 }58 59 60 int main()61 {62 //freopen("D:\\input.txt","r",stdin);63 while(~scanf("%d",&n))64 {65 for(int i=1;i<=n;i++) G[i].clear();66 for(int u=1;u<=n;u++)67 {68 while(true)69 {70 int x;71 scanf("%d",&x);72 if(x==0) break;73 G[u].push_back(x);74 }75 }76 find_scc();77 78 for(int i=1;i<=scc_cnt;i++) in[i]=out[i]=1;79 for(int u=1;u<=n;u++)80 {81 for(int i=0;i<G[u].size();i++)82 {83 int v=G[u][i];84 if(sccno[u]!=sccno[v]) in[sccno[v]]=out[sccno[u]]=0;85 }86 }87 int a=0,b=0;88 for(int i=1;i<=scc_cnt;i++)89 {90 if(in[i]) a++;91 if(out[i]) b++;92 }93 int ans=max(a,b);94 if(scc_cnt==1) a=1,ans=0;95 printf("%d\n%d\n",a,ans);96 }97 return 0;98 }
POJ 1236 Network of School
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。