O(N^2)
思路:我们首先将不发送信息的所有奶牛标记为非循环
然后 我们再次遍历奶牛 将转发信息到非循环奶牛的任何奶牛也标记为非循环奶牛
我们重复此过程n次 实际就是在标记所有非循环的奶牛链
所以最后没有被标记的奶牛必然是处于循环的
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int ne[N], nonloop[N];
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>ne[i];
if(ne[i]==0)
nonloop[i]=1;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(nonloop[ne[j]])
nonloop[j]=1;
int cnt=0;
for(int i=1; i<=n; i++)
cnt+=nonloop[i];
cout<<cnt;
return 0;
}
O(N)
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
bool st[N];
int loop[N], ne[N];
bool isloop(int u)
{
if(loop[u]!=-1) return loop[u];
if(u==0) return false;
if(st[u]) return true;
st[u]=true;
loop[u]=isloop(ne[u]);
st[u]=false;
return loop[u];
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>ne[i];
memset(loop, -1, sizeof loop);
int cnt=0;
for(int i=1; i<=n; i++)
cnt+=isloop(i);
cout<<n-cnt;
return 0;
}
第二种用dfs还是O(n)吗
请教一下解法一的两层遍历是为什么呀
n^2次判断 确保所有的n头奶牛都被排查过是否陷入循环
感觉是这样 我也是这么ac的但是想不太明白,大佬可以详细说说吗
我把思路改的详细了一点 可以去看一下
nonloop[N]
bool也行吧确实