[백준] 25195번. Yes or yes

문제

https://www.acmicpc.net/problem/25195

 

주의 사항

시간초과 나서 graph를 전역 변수로 놨더니 괜찮아 졌다.

 

풀이

dfs로 풀었다.

#include <iostream>
#include <vector>
using namespace std;
bool possible;
int visit[100001] = { 0, };
int bomb[100001] = { 0, };
vector<vector<int>>graph;

void dfs(int node)
{
	if (possible) { return; }

	bool move = false;
	for (int i = 0; i < graph[node].size(); i++)
	{
		int next = graph[node][i];
		if (visit[next] != 0) continue;
		if (bomb[next] != 0) { move = true; continue; }
		move = true;
		visit[next]++;
		dfs(next);
	}
	if (!move) { possible = true; }
}
int main()
{
	//input
	int N, M;
	cin >> N >> M;
	possible = false;
	graph= vector<vector<int>>(N+1);
	

	//graph
	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
	}

	//fan club location (bomb)
	int bombCount;
	cin >> bombCount;
	for (int i = 0; i < bombCount; i++) 
	{ int b; cin >> b; bomb[b]++; }

	//START DFS
	if (bomb[1] != 0) { cout << "Yes"; return 0; }
	dfs(1);

	//result
	if (possible) { cout << "yes"; }
	else { cout << "Yes"; }
}