Codeforces Round #357 (Div. 2) D. Gifts by the List

http://codeforces.com/contest/681/problem/D

간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다

그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)

N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데

각 N명의 사람들은 list의 맨왼쪽에 있는 명단부터 차례대로 봐가면서 무조건 가장 처음으로 등장하는 조상에게 선물을 줘야한다. 그리고 만약 list를 끝까지 다 봤는데도 자신의 조상이 나오지 않는다면 아무에게도 선물을 주지 못하고 집에간다. 문제는 N명의 사람모두가 자기가 선물을 주고 싶은 사람에게 선물을 줄 수 있도록 하는 list를 구하는 것이다. 만약 이러한 list가 존재하지 않는다면 -1을 출력한다.

우선 한가지 확실한 것은 N명의 사람들이 선물을 주고싶어하는 모든 사람들은 list에 존재해야하고 딱 이 사람들만 있으면 된다는 것이다. 그런데 중요한건 순서를 어떻게 할 것인가 이다.

선물을 받아야 할 사람 ai와 aj가 있다고 가정해보자. 조금만 생각해보면 한가지 확실한것은, 만약 ai 가 aj의 자손이라면 ai는 list 상에서 무조건 aj보다 앞서야한다. 왜냐하면 aj가 앞선다면 ai에게 선물을 주고싶은 사람은 ai에게 선물을 주고싶어도 list상에서 앞선 aj에게 선물을 줘야만 하기 때문이다.(ai 에게 선물을 주고싶은 사람은 ai의 자손이고, ai는 aj의 자손이기 때문에 ai에게 선물을 주고싶은사람은 결국 aj의 자손도 되기 때문이다.) 그럼 우선 자손-조상 관계인 노드쌍이라면 자손이 조상보다 앞서도록 정렬을 해보자. 방법은 '위상 정렬' 로 하면 된다. dfs를 돌려서 자식들에대해 다 돌고 반환될때 벡터에 push를 해주자.

그러고 나면 이제 list에 들어가야 할 노드들을 이 정렬된 순서대로 하나씩 넣으면서 

각 N명의 사람들이 list를 보고 실제로 누구한테 선물을 주게 되는지를 구해야한다.

그리고 각 N명의 사람들 모두가 본인이 원래 선물을 주고싶었던 사람과 실제로 선물을 주게 되는사람이 같으면 YES이고 한명이라도 원래 주고싶었던 사람에게 못주게된다면 NO이다.

그렇다면 각 N명의 사람들에 대해 list를 보고 실제로 선물을 주게 될 사람은 누구일까?

조상들중에서 list상에서 가장 앞서는 놈일 것이다. 그렇다면 list 상에 차례로 정렬된 노드들을 넣으면서 그 노드의 모든 자손들 중에 아직 실제로 선물을 주게 될 사람이 정해 지지 않은 노드는, list를 보면 나에게 먼저 선물을 주게 되어있기 때문에 표시해준다. 왜냐하면 아직 정해지지 않았다는 것은 조상들중에 아직 list에 아무도 들어가지 않았다는 것을 의미하기 때문에 이번에 list에 추가된 노드가 조상들중 list에서 가장 앞쪽에 나오는 놈이기 때문이다. 즉 위상정렬 순서대로 list에 하나씩 넣으며 서브트리에 대해 실제 선물을 주게될 사람을 N개의 노드에 대해 구해주고 마지막에 원래 주고싶었던놈과 같은지 N놈에 대해 확인해주면된다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int N,M;
vector<int> G[100003];
int isGiven[100003];
int give[100003];
int visited[100003];
int r[100003];
vector<int> sorted;
void dfs(int here){
    if(visited[here]) return;
    visited[here] = 1;
    for(int there : G[here]){
        dfs(there);
    }
    sorted.push_back(here);
}
void dfs2(int here, int val){
    if(r[here]!=-1) return;
    r[here] = val;
    for(int there : G[here]){
        dfs2(there, val);
    }
}
int main() {
    fastio();
    cin >> N >> M;
    for(int i = 0 ; i < M; i++) {
        int a,b;
        cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
    }
    for(int i = 0 ; i < N; i++){
        cin >> give[i];
        give[i]--;
        isGiven[give[i]]=1;
    }
 
    for(int i = 0 ; i < N; i++) 
        dfs(i);
 
    vector<int> ans;
    memset(r,-1,sizeof(r));
    for(int node : sorted){
        if(!isGiven[node]) continue;
        ans.push_back(node);
        dfs2(node, node);
    }
 
    for(int i = 0 ; i < N; i++) {
        if(give[i] != r[i]) {
            cout << "-1";
            return 0;
        }
    }
 
    cout << ans.size() << "\n";
    for(int node : ans){
        cout << node+1 << "\n";
    }
 
 
    return 0;
}