容易想到,如果某个人x得到人自己发出去的信息,则图上存在一个环,于是整个问题就变成了求图上最小环的算法.
对题目进行数据抽象(数学建模): 有一个图,
使用dfs法,在dfs遍历的过程中,如果遇到了一个点x,且vis[x] == 1,表示x已经访问过,则这个存在环.
这个好像,很难,先考虑简单的问题,如何求哪些点在环上呢?
好现在知道了: 每个点都在环上,求最小环
又因为,根据题意,每个点的出度必是1
从上面的前提条件,得到:
证明1:
因为,每个点的出度为1,所以每个的点都出发一条边,共有
根据所学习的树的知识,一个无环图最多有
证明2:
假定无环,则必存一个条链(路),这个链的结尾的出度为1,与前提矛盾,证毕
如果不存在单环,那么必然存在一个点的出度至少是
我看luogu上面的解析有使用并查集的,我很惊奇,这个我没有想出来还要这样做,于是我看了看.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int maxe = 1e6+5;
struct linkList {
typedef struct {int u,v,w,next;} edge;
edge e[maxe];
int h[maxn],edge_cnt=0;
linkList(){
edge_cnt=0;
memset(h,-1,sizeof(h));
}
//遍历点u 周围点
template<typename U>
void for_each(int u,U func){
for(int i = h[u] ; i !=-1;i = e[i].next)
func(e[i].u,e[i].v,e[i].w); //u v w
}
void add(int u,int v,int w=0){
e[edge_cnt] = {u,v,w,h[u]};
h[u] = edge_cnt++;
}
void add2(int u,int v,int w=0){
add(u,v,w);
add(v,u,w);
}
//下标访问
edge& operator[](int i){ return e[i]; }
//返回head[u]
int operator()(int u){ return h[u]; }
} e;
template<typename T = int,int siz = maxn>
struct myqueue{
T a[siz+5];
//tail 指向最后一个元素后面一个位置
//head 指向第一个元素
int head = 0,tail=0;
void clear() { head =tail = 0;}
void push(T b) { a[tail++] = b;}
void pop(){head++;}
void pop_back(){tail--;}
T front() { return a[head];}
T back() { return a[tail-1];}
bool empty() { return head == tail;}
int size() { return tail-head;}
};
int n;
int indeq[maxn]; //每个点的入度,入度为0,表示不在环上
bool vis[maxn];
myqueue<int> que; //队列,进行topsort
int ans = 0x7f7f7f7f;
//把那些,不在环上的点标记
void topsort(){
while (!que.empty()) {
int u = que.front();
// cout << u << endl;
que.pop();
for(int ed = e.h[u]; ~ed; ed = e[ed].next)
{
int v = e[ed].v;
if( --indeq[v] == 0) {
que.push(v);
}
}
}
}
int dfs(int u) {
vis[u] = 1;
int cnt = 1;
// cout << "dfs " << u << endl;
for(int ed = e.h[u]; ~ed; ed = e[ed].next)
{
int v = e[ed].v;
if( indeq[v] == 0 || vis[v]) continue;
cnt += dfs(v);
}
return cnt;
}
int main () {
std::cin >> n;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
int t;
std::cin >> t;
e.add(i,t);
indeq[t]++;
}
//入度为0的点加入队列
// cout << endl;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
if( indeq[i] == 0)
que.push(i);
// cout << indeq[i] << " ";
}
// cout << endl;
topsort();
//求最小环
for(int i =1;i<=n;i++) {
if( indeq[i] == 0 || vis[i]) continue;
int t = dfs(i);
if( ans > t)
ans = t;
}
cout << ans << endl;
return 0;
}
使用是tranjan,dfn,对dfs树进行编号的思想,当返祖边存在时,有环,具体看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
* 先找到环上的最小编号的点,然后从这个点开始
* */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int n;
int a[200005];
bool vis[200005] = {0}; //是否已经访问过
int dnf[200005];
bool isRn[200005] = {0}; //是不是最小反回点
int maxRn[200005] = {0}; //最小反回点的最大接触值
int ans = 0x7f7f7f7f;
void dfs(int x,int idx){
vis[x] = 1; //已经访问
dnf[x] =idx;
int next = a[x];
if( vis[next] == 0) { //没有访问过
dfs(next,idx+1);
}
else { //已经访问过
isRn[next] = 1;
maxRn[next] = x;
}
//回溯
if( isRn[x])
ans = min(ans,dnf[maxRn[x]] -dnf[x] +1);
}
int main(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
if( vis[i] == 0)
dfs(i,1);
printf("%d",ans);
return 0;
}