AcWing 3465. 病毒溯源--y总原版代码

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 3465. 病毒溯源--y总原版代码原题链接中等

作者：

小染 , 2021-05-05 14:21:31 , 所有人可见 , 阅读 1914

11

3

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = 10010;

int n;
int h[N], e[M], ne[M], idx;
int son[N];
bool st[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    int res = 0;
    son[u] = -1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        int d = dfs(j);
        if (res < d) res = d, son[u] = j;
        else if (res == d) son[u] = min(son[u], j);
    }
    return res + 1;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
    {
        int cnt;
        scanf("%d", &cnt);
        while (cnt -- )
        {
            int x;
            scanf("%d", &x);
            add(i, x);
            st[x] = true;
        }
    }

    int root = 0;
    while (st[root]) root ++ ;

    printf("%d\n", dfs(root));
    printf("%d", root);
    while (son[root] != -1)
    {
        root = son[root];
        printf(" %d", root);
    }

    return 0;
}

7 评论

ZZZHHHXXX 8个月前

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int h[N],e[N],ne[N],idx,d[N],son[N],n,m,vis[N]; 
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u){
    if(d[u])return d[u];
    d[u]=1;
    son[u]=-1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        if(d[u]<d[j]+1){
            d[u]=d[j]+1;
            son[u]=j;
        }else if(d[u]==d[j]+1){
            son[u]=min(son[u],j);
        }
    }
    return d[u];
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=0;i<n;i++){
        int k,b;
        cin>>k;
        while(k--){
            cin>>b;
            add(i,b);
            vis[b]=1;
        }
    }
    int root=-1;
    while(vis[++root]);
    dfs(root); 
    cout<<d[root]<<endl;
    cout<<root;
    while(~son[root]){
        cout<<" "<<son[root];
        root=son[root];
    }
    return 0;
}