L2 - 2 病毒溯源

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10010;

vector<int>v[N];
bool isroot[N];
vector<int> path;
vector<int>temppath;
int ans = 0;

void dfs(int root, int len){
    if(v[root].size() == 0){
        if(len < ans) return;
        if(len > ans){
            ans = len;
        path = temppath;
        }
    }
    for(int i = 0; i < v[root].size(); i++){
        temppath.push_back(v[root][i]);
        dfs(v[root][i],len + 1);
        temppath.pop_back();
    }
}

bool cmp(int a, int b){
    return a < b;
}

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int k ; cin >> k;
        int x; 
        for(int j = 1; j <= k; j++){
            cin >>x;
            v[i].push_back(x);
            isroot[x] = 1;
        }
        if(v[i].size()) sort(v[i].begin(), v[i].end(), cmp);//从小到大排序就可以实现优先选择较小的
    }
    vector<int>root;
    for(int i = 0; i < n; i++){
        if(isroot[i] == 0){
            root.push_back(i);
            break;
        }
    }
    for(int i = 0; i < root.size();i++){
        temppath.clear();
        temppath.push_back(root[i]);
        dfs(root[i],1);
    }
    cout  << ans << endl;
    for(int i = 0; i < path.size(); i++){
        if(i) cout <<" ";
        cout << path[i];
    }
    return 0;
}