알고리즘
백준 25195번 Yes or yes C++
영춘권의달인
2022. 10. 28. 17:03
https://www.acmicpc.net/problem/25195
25195번: Yes or yes
첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는
www.acmicpc.net
dfs
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int n, m;
vector<vector<int>> graph;
vector<bool> gomGom;
bool meet = true;
void Dfs(int node, bool isGomGom) {
if (gomGom[node]) isGomGom = true;
if (graph[node].size() == 0) {
if (isGomGom == false) meet = false;
}
else {
for (auto next : graph[node]) Dfs(next, isGomGom);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
graph = vector<vector<int>>(n + 1, vector<int>());
gomGom = vector<bool>(n + 1, false);
for (int i = 0; i < m; i++) {
int start, end;
cin >> start >> end;
graph[start].push_back(end);
}
int S;
cin >> S;
for (int i = 0; i < S; i++) {
int s;
cin >> s;
gomGom[s] = true;
}
Dfs(1, false);
if (meet) cout << "Yes";
else cout << "yes";
}