로곡-2661 정보 전달
1403 단어 알고리즘 문제
입력 출력 예제 입력 예제 #1:5 2 4 2 3 1
샘플 내보내기 #1:3
해석: 모든 학우를 하나의 노드로 보고 말을 방향이 있는 것으로 간주한다. 그것이 바로 그림에서 가장 작은 고리 문제를 찾는 것이다. 그러면 한 번의 dfs만 있으면 된다. 우리는 모든 점에 dfs순으로 번호를 매긴다. 그러면 표시가 있는 점까지 두루 돌아다닐 때 그 표지가 지금부터 시작된 가장 작은 DFS 번호보다 작으면 이미 두루 돌아다녔고 고리가 존재하지 않는다. 그렇지 않으면 하나의 고리이다. dfs순이 나쁘면 고리의 크기를 얻는다.
#include
#define N 200003
using namespace std;
int a[N]={0};
int n=0;
int vis[N]={0};
int ret=N+1;
int t=0;
int dfs(int x){
int start=t+1;
while(!vis[x]){
vis[x]=++t;
x=a[x];
}
if(start>vis[x]) return N+1;
else return t-vis[x]+1;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(!vis[i]){
ret=min(ret,dfs(i));
}
}
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[못 푼 문제] 백준 10989번sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.