NOIP2015信息传递 题解

题目链接

说起来是个水题。

然而我好像,做的复杂了。

这个题问能进行几次,实际上是求最小的环。

然后想都没想就直接写边表用Tarjan做了。

每次找到环记一下数,对于大于2的环每次求最小值来更新答案。

还是很快切掉了。

代码(C++11):

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
#include<iostream>
#include<cstdio>
#include<stack>

using LL=long long;

const int inf=0x7fffffff;
const int maxn=2e6+10;

typedef struct EdgeNode
{
int to;
EdgeNode *next;
EdgeNode(int to,EdgeNode *nxt):to(to),next(nxt){}
}*Edge;

struct Point
{
Edge head;
int dfn,low;
bool vis;
Point()
{
this->head=nullptr;
this->dfn=this->low=0;
this->vis=0;
}

inline void add(int to)
{
this->head=new EdgeNode(to,this->head);
}

}pot[maxn];

int n,Time=0,ans=inf;
std::stack<int> S;

void Tarjan(int pos)
{
pot[pos].dfn=pot[pos].low=++Time;
S.push(pos);
pot[pos].vis=true;
for(Edge node=pot[pos].head;node!=nullptr;node=node->next)
{
int to=node->to;
if(!pot[to].dfn)
{
Tarjan(to);
pot[pos].low=std::min(pot[pos].low,pot[to].low);
}
else if(pot[to].vis)
pot[pos].low=std::min(pot[pos].low,pot[to].dfn);
}
if(pot[pos].dfn==pot[pos].low)
{
int now,cnt=0;
do
{
now=S.top();
S.pop();
pot[now].vis=false;
cnt++;
}
while(now!=pos);
if(cnt>1)
ans=std::min(ans,cnt);
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
pot[i].add(t);
}
for(int i=1;i<=n;i++)
if(!pot[i].dfn)
Tarjan(i);
printf("%d\n",ans);
return 0;
}

不过,根本不用这么麻烦呀!

你看这个图,每个点的出度不超过2,显然边表的next压根没用。

所以啊!

直接去掉,开一个数组只记录每个点连着的点,然后把递归里面的那个循环扔了就好了!

但是懒得改了,当做练习板子吧……