被Hack的代码:
# include <bits/stdc++.h>
# define reg register
typedef long long ll;
using namespace std;
int n, a[200005], du[200005], f[200005], minx = 1e9, s[200005], x;
queue <int> q;
int find (int x) {
return f[x] == x ? x : f[x] = find (f[x]);
}
int main () {
ios::sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
// freopen ("dmes.in", "r", stdin);
//
// freopen ("dmes.out", "w", stdout);
cin >> n;
for (reg int i = 1; i <= n; ++ i) {
f[i] = i;
cin >> a[i];
++ du[a[i]];
}
for (reg int i = 1; i <= n; ++ i)
if (! du[i])
q.push (i);
while (! q.empty ()) {
x = q.front ();
q.pop ();
if (! -- du[a[x]])
q.push (a[x]);
}
for (reg int i = 1; i <= n; ++ i)
if (du[i])
f[find (i)] = find (a[i]);
for (reg int i = 1; i <= n; ++ i)
if (du[i])
++ s[find (i)];
for (reg int i = 1; i <= n; ++ i)
if (du[i])
minx = min (minx, s[find (i)]);
cout << minx;
return 0;
}
/*
5
2 4 2 3 1
*/
Hack.in数据生成器:
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"200000\n";
for(int i=1;i<200000;++i)
cout<<i+1<<' ';
cout<<1;
return 0;
}
Hack.out
200000
我输出1,有没有题解可以撤暂时不知道,但是请求添加Hack