CodeForces 681D Gifts by the List (树上DFS)

题意：一个家庭聚会，每个人都想送出礼物，送礼规则是，一个人，先看名单列表，发现第一个祖先就会送给他礼物，然后就不送了，如果他没找到礼物他会伤心的离开聚会！告诉你m个祖先关系，

和每个人想给谁送！让你求出名单列表！

析：这个题，真是没想到啊，还是看的题解，首先要知道的是，如果自己和父结点送的人不一样，并且自己不是给自己的，那么就是无解，为什么呢？是这样的，假设自己和父结点送的人不一样，并且也不是给自己的，

那么一定是给自己的某个祖先，而父结点也是自己的某个祖先，那么不是同一个人，必定一个是另一个祖先，那么矛盾，所以一定是这样的，根据这个还不能确定出来结果，如果没人给自己送，那么这个结点就可以不要了，

在搜索时的有一个原则，用不到的就不要放上，更加简洁，也就是说，如果一个人不给自己送，那么这个人就没有存在的必要了，为什么呢？你想想，如果别人还给自己送了，自己又没给自己送，说明还有人是自己的祖先，

那么另一个人应该送和自己一样的人。对于搜索是先从祖先向下面进行搜索，然后判断能不能成立。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

vector<int> G[maxn],ans;

int a[maxn];

bool b[maxn];

bool ok;

void dfs(int u, int fa){

    for(int i = 0; i < G[u].size(); ++i){

        int v = G[u][i];

        if(v == fa)  continue;//判断是不是和父结点一样

        if(a[v] != a[u] && a[v] != v){  ok = true;  return ; }//矛盾，直接结束

        dfs(v, u);

    }

    if(a[u] == u)   ans.push_back(u);//如果不给自己送，那么就没有存在的必要了

}

int main(){

    int n, m, u, v;

    cin >> n >> m;

    while(m--){

        cin >> u >> v;

        G[u].push_back(v);

        G[v].push_back(u);

        b[v] = true;//查找祖先

    }

    for(int i = 1; i <= n; ++i)  cin >> a[i];

    ok = false;

    for(int i = 1; i <= n; ++i)

        if(ok)  break;

        else if(!b[i])  dfs(i, -1);//搜索

    if(ok)  cout << "-1\n";

    else{

        cout << ans.size() << endl;

        for(int i = 0; i < ans.size(); ++i)

            cout << ans[i] << endl;

    }

    return 0;

}

巴特西

CodeForces 681D Gifts by the List (树上DFS)

最新文章

热门文章