博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ1236(Network of Schools)
阅读量:4841 次
发布时间:2019-06-11

本文共 3009 字,大约阅读时间需要 10 分钟。

这题大意是给一个有向图,求至少给多少个结点发消息能使消息传遍整个网络,并进一步求出至少添加多少条边能使对图中任意一个结点发消息都能使消息传遍整个网络。可以先用kosaraju将强连通分支缩点,得到原图的基图,然后统计入度为0的连通分量个数和出度为0的连通分量个数,入度为0的必须给它发消息,入度不为0的不必给发消息,所以第一问所求即为缩点后的图中入度为0的个数,至于第二问,只需将入度为0的结点与出度为0的结点连接即可满足要求,最少需加边数目为两者之中的较大者,需注意的是,单只有一个连通分量时,输出结果为0 。这题第一次提及后TLE,原因竟是N不够大,为什么不是RE呢?

View Code
1 #include 
2 #include
3 #define CLR(a) (memset(a,0,sizeof(a))) 4 #define N 105 5 struct node 6 {
7 int v; 8 struct node *next; 9 }; 10 struct node *in[N],*out[N]; 11 char vis[N]; 12 int ord[N],id[N],din[N],dout[N],cnt,n; 13 void addEdge(int u,int v) 14 {
15 struct node *p,*q; 16 p=(struct node*)malloc(sizeof(struct node)); 17 q=(struct node*)malloc(sizeof(struct node)); 18 p->v=v; 19 p->next=out[u],out[u]=p; 20 q->v=u; 21 q->next=in[v],in[v]=q; 22 } 23 void dfs(int u) 24 {
25 int v; 26 struct node *p=out[u]; 27 vis[u]=1; 28 while(p) 29 {
30 v=p->v; 31 if(!vis[v]) dfs(v); 32 p=p->next; 33 } 34 ord[++cnt]=u; 35 } 36 void rdfs(int u) 37 {
38 int v; 39 struct node *p=in[u]; 40 vis[u]=1,id[u]=cnt; 41 while(p) 42 {
43 v=p->v; 44 if(!vis[v]) rdfs(v); 45 p=p->next; 46 } 47 } 48 void kosaraju() 49 {
50 int i,j,t,ans1,ans2; 51 struct node *p; 52 CLR(vis); 53 for(i=1,cnt=0;i<=n;i++) 54 {
55 if(!vis[i]) dfs(i); 56 } 57 CLR(vis); 58 for(t=n,cnt=0;t>0;t--) 59 {
60 i=ord[t]; 61 if(!vis[i]) 62 {
63 cnt++; 64 rdfs(i); 65 } 66 } 67 CLR(din),CLR(dout); 68 for(i=1;i<=n;i++) 69 {
70 p=out[i]; 71 while(p) 72 {
73 j=p->v; 74 if(id[i]!=id[j]) dout[id[i]]++,din[id[j]]++; 75 p=p->next; 76 } 77 } 78 for(i=1,ans1=0,ans2=0;i<=cnt;i++) 79 {
80 if(!din[i]) ans1++; 81 if(!dout[i]) ans2++; 82 } 83 ans2=ans1>ans2?ans1:ans2; 84 if(cnt==1) ans2=0; 85 printf("%d\n%d\n",ans1,ans2); 86 } 87 void clr() 88 {
89 int i; 90 struct node *p; 91 for(i=1;i<=n;i++) 92 {
93 p=out[i]; 94 while(p) 95 {
96 out[i]=p->next,free(p),p=out[i]; 97 } 98 p=in[i]; 99 while(p) 100 {
101 in[i]=p->next,free(p),p=in[i]; 102 } 103 } 104 } 105 int main() 106 {
107 int i,j; 108 while(scanf("%d",&n)!=EOF) 109 {
110 for(i=1;i<=n;i++) 111 {
112 while(scanf("%d",&j)&&j) 113 {
114 addEdge(i,j); 115 } 116 } 117 kosaraju(); 118 clr(); 119 } 120 return 0; 121 }

 

转载于:https://www.cnblogs.com/algorithms/archive/2012/04/02/2430007.html

你可能感兴趣的文章
C++cctype软件包函数摆脱,ASCII码!
查看>>
saltstack笔记
查看>>
(转载)TP5_自定义分页样式
查看>>
Spring3.2 和 jdk8 运行时有冲突
查看>>
WordPress4.1新的函数介绍
查看>>
list<T> 排序
查看>>
结对2.03
查看>>
【vue】vue如何创建一个项目
查看>>
简单的linux压力测试工具webbench
查看>>
ImageLunBo_shape+XML
查看>>
php实现设计模式————单例模式
查看>>
Python OOP(面向对象编程)
查看>>
MySQL安装与测试
查看>>
使用JDK自带的VisualVM进行Java程序的性能分析
查看>>
mysql语句记录
查看>>
总结面试题
查看>>
Win8AX博客园应用隐私声明
查看>>
windows中的软链接硬链接等
查看>>
如何在本地调试微信接口
查看>>
Java二分法
查看>>