[BOJ] 25195번 : Yes or yes C++ 풀이

간단한 그래프 문제이다.
1번 노드를 기준으로 리프 노드까지 탐색하고, 이때 지나갈 수 없는 노드의 번호가 주어진다. 이때 리프 노드까지 정상적으로 탐색할 수 있는가?를 묻고 있다. 

1번 노드를 기준으로 BFS or DFS를 돌리고, 리프 노드들을 확인해 하나라도 도달한 케이스가 있는지 확인하면 모든 조건을 만족할 수 있다. 현재 그래프가 유향 그래프로 주어지므로, 리프 노드는 간선의 개수가 0인 노드들이 될 것이다. 이 노드들을 모두 확인했을 때 도달한 적이 있다면 yes를, 하나라도 도달할 수 없다면 Yes를 출력하자.

 

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, M, S, visited[NUM];

vector<int> adj[NUM];


void dfs(int curr) {
    for (int next : adj[curr]) {
        if (visited[next] != 0) continue;
        visited[next] = 1;
        dfs(next);
    }
}

void init() {  
    memset(visited, 0, sizeof(visited));
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }

    visited[1] = 1;

    cin >> S;
    for (int i=0; i<S; i++) {
        int x;
        cin >> x;
        visited[x] = -1;
    }
    if (visited[1] != -1) dfs(1);

    bool flag = false;

    for (int i=1; i<=N; i++) {
        if (adj[i].size() == 0 && visited[i] == 1) flag = true;
    }
    if (!flag) cout << "Yes" << '\n';
    else cout << "yes" << '\n';

} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}