暴力
- 首先打暴力
- 以每个点为起点, 从该点出发, 能不能构成一个环, 若构成一个环则更新最大值
- 时间复杂度最坏 $ n ^ 2 $,超时
暴力代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int q[N];
bool st[N];
int res;
void dfs(int start, int u, int step)
{
st[u] = true;
if (q[u] == start)
{
res = max(res, step + 1);
return ;
}
if (!st[q[u]]) dfs(start, q[u], step + 1);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
for (int i = 1; i <= n; i ++ )
{
dfs(i, i, 0);
memset(st, false, sizeof st);
}
cout << res << endl;
return 0;
}
考虑优化剪枝
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int q[N];
bool st[N];
int res;
// 一个性质, 只要发现了,题就很好写了。
// 只要前面这个点与其他点构成过一个环, 就不能再与其他点构成环
// 题目中的每个点只有一条出边。如果已经构成一个环,如果还能连接另一个环,则至少包含两条出边,矛盾。
// 因此每个点至多只能存在一个环中。
// 然后判断这个点是否构成过环, 如果构成过, 直接剪掉,否则找环
// 起点, 当前点, 步数
bool dfs(int start, int u, int step)
{
st[u] = true; // 这个点已经搜过且默认有环
if (q[u] == start) // 这个点的下一个位置是起点,构成一个环
{
res = max(res, step + 1); // 更新答案
return true; // 已经找到环
}
// 如果下一个点没有遍历过或者不在环里
if (!st[q[u]])
{
st[q[u]] = dfs(start, q[u], step + 1);
// 当前点构成环
if (st[q[u]]) return true;
}
// 这个点不能构成环
return false;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
for (int i = 1; i <= n; i ++ )
if (!st[i]) dfs(i, i, 0); // 如果这个点没构成过环
cout << res << endl;
return 0;
}
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int q[N];
bool st[N];
int res;
bool dfs(int start, int u, int step)
{
st[u] = true;
if (q[u] == start)
{
res = max(res, step + 1);
return true;
}
if (!st[q[u]])
{
st[q[u]] = dfs(start, q[u], step + 1);
if (st[q[u]]) return true;
}
return false;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
for (int i = 1; i <= n; i ++ )
if (!st[i]) dfs(i, i, 0);
cout << res << endl;
return 0;
}
这个优化好像还是
n^2
复杂度eg: 2 3 4 5 5
咳咳,我没咋具体算,时间太久都已经忘了
感觉有点麻烦了,还有其他更优的解法吗
我这写的可能有点麻烦,只要根据那个性质去写好了
嘿嘿同学,我用了另一个做法做出来了,在我另一篇题解里,提高课的板子。