도론-최소환 문제(dfs+ 및 조사집)

제목 설명

nn의 학우(번호 11에서 nn)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 번호가ii인 학우의 정보 전달 대상은 번호가T 이다아이티의 동창.
게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?

입력 형식

모두 22줄입니다.
11 행에는 nn 개인을 나타내는 양의 정수 nn이 있습니다.
22행에는 nn개의 양의 정수 T 가 공백으로 구분됩니다.1,T_2,\cdots\cdots,T_nT1, T2,..., Tn, 그중 ii의 정수 TiTi는 ii로 번호를 매긴 학생의 정보 전달 대상이 T 임을 나타낸다iTi의 동창,Ti\leq nTi ≤n 및 Ti eq iTi≠i .

출력 형식

11개의 정수는 게임이 모두 몇 라운드를 진행할 수 있는지를 나타낸다.

출력 샘플 가져오기

#1 복사 입력

5
2 4 2 3 1

출력 #1 복사

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int inf=1e9;
const int N=200020;
int n,m,step,ans;
int d[N],num[2010],e[N],ne[N],idx,w[N],st[2010],h[N],f[N];
int a[N],vis[N],cnt[N];
typedef pair PII;



/*   
void  dfs(int x,int s)
{
    if(f[x]) return;// 
    if(vis[x])// 
    {
        ans=min((s-cnt[x]),ans);
        return ;
    }
    vis[x]=1;
    cnt[x]=s;
    dfs(a[x],s+1);
    f[x]=1;
}

int main(){
    cin>>n;
    ans=inf;
    idx=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
      dfs(i,1);
    }
    cout<>n;
    ans=inf;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Union(i,a[i]);
    }
    cout<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2236 Wireless Network 간편한 검색 및 수집

The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

도론-최소환 문제(dfs+ 및 조사집)

제목 설명

입력 형식

출력 형식

출력 샘플 가져오기

좋은 웹페이지 즐겨찾기