文档章节

图上求最小环

o
 osc_g8254g7s
发布于 2019/08/19 22:53
字数 467
阅读 11
收藏 0
ind

精选30+云产品,助力企业轻松上云!>>>

最近做了道水题题,信息传递,题目要求就是求出有向图的最小环。

做完乍一看题解有好多好多种办法,在此整理一下。

我对于这道题的做法是:

由于每个点最多连出一条边,所以可能存在两个环相连的情况,所以对于入度为0的点删掉就好,然后不断删不断删,

直到删到图上仅有环,就一个一个求一求环的大小,取最小的那一个。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 200005
 6 
 7 using namespace std;
 8 
 9 int nxt[maxn],ans=2147483647,ind[maxn],n;
10 bool vis[maxn];
11 
12 inline void cancel(int k)
13 {
14     int e=nxt[k];
15     ind[k]=0; ind[nxt[k]]--; nxt[k]=-1;
16     if(ind[e]==0) cancel(e);
17 }
18 
19 inline void dfs(int x_now,int st,int len)
20 {
21     if(x_now==st&&len!=0)
22     {
23         vis[x_now]=true;
24         ans=min(ans,len);
25         return;
26     }
27     else
28     {
29         vis[nxt[x_now]]=true;
30         dfs(nxt[x_now],st,len+1);
31     }
32     return;
33 }
34 
35 int main()
36 {
37     scanf("%d",&n);
38     for(int i=1;i<=n;i++)
39     {
40         scanf("%d",&nxt[i]);
41         ind[nxt[i]]++;
42     }
43     for(int i=1;i<=n;i++)
44         if(ind[i]==0&&nxt[i]!=-1) cancel(i);
45     for(int i=1;i<=n;i++)
46         if(nxt[i]!=-1&&!vis[i]) dfs(i,i,0);
47     printf("%d\n",ans);
48     return 0;
49 }

 

一开始我还想用缩点求每个强连通分量的大小,后来一想,强联通分量是极大的子图,所以对于大环中有小环的情况,它只能求出

大环而求不出小环。

例如:

所以这种愚蠢的想法就被pass了。


 

还有一种做法就是用带权并查集做,权维护的是该点到自己父节点的距离。

如果某一条边连接了两个父节点相同的点,说明它们构成环,环的大小是...,

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

格式编号始终显示2个小数位 - Format number to always show 2 decimal places

问题: I would like to format my numbers to always display 2 decimal places, rounding where applicable. 我想将数字格式化为始终显示2个小数位,并在适用的情况下四舍五入。 Examples...

富含淀粉
40分钟前
22
0
Docker可视化工具Portainer

1 前言 从没想到Docker也有可视化的工具,因为它的命令还是非常清晰简单的。无聊搜了一下,原来已经有很多Docker可视化工具了。如DockerUI、Shipyard、Rancher、Portainer等。查看对比了一番...

南瓜慢说
42分钟前
20
0
日志系统新贵 Loki,真香!!

最近,在对公司容器云的日志方案进行设计的时候,发现主流的ELK或者EFK比较重,再加上现阶段对于ES复杂的搜索功能很多都用不上最终选择了Grafana开源的Loki日志系统,下面介绍下Loki的背景。...

庞陆阳
55分钟前
14
0
jQuery获取select onChange的值 - jQuery get value of select onChange

问题: I was under the impression that I could get the value of a select input by doing this $(this).val(); 我的印象是我可以通过执行$(this).val();来获取选择输入的值$(this).val()......

javail
今天
13
0
道翰天琼解密宇宙信息大脑三者最核心奥秘,破解认知智能基础理论(群聊形式)

三体论是探索研究宇宙,信息和人类大脑三者关系的理论体系。是认知智能的奠基理论体系之一。宇宙和信息,信息和人类大脑,人类大脑和宇宙,三者之间存在着某种未被完全揭示的奥秘。三体论的核...

jackli2020
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部