s1977. 信息中继--------->图论,并查集,DFS(不会)!
作者:
cyuyu
,
2022-04-30 20:39:38
,
所有人可见
,
阅读 162
代码:
#include<iostream>
using namespace std;
const int N=1010;
int st[N];
int a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0)
st[i]=1;
}
for(int i=1;i<=n;i++){//双层循环,确定每一头奶牛在通信线路上的状态!!!!
for(int j=1;j<=n;j++){
if(st[a[j]])
st[j]=1;
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=st[i];
}
cout<<ans<<endl;
return 0;
}
又是一道不咋会的题目!本题目可以采用暴力方式,判断每一头奶牛是否在循环中,如上述代码,
注意一定要使用双层循环,为什么呢,因为要确保每一头奶牛都能判断到,如果只有一层循环,可能会有
很多奶牛不被判断是否在循环中,这是我要学习的地方!!!
本题目也可以使用图论的dfs,并查集的知识,菜鸡还没学图论知识,标记!!!