[백준] 26146 즉흥 여행(Easy)

문제

철민이는 종강을 기념하여 �$ N $개의 나라로 즉흥 여행을 떠나기로 했다.

철민이의 조사에 따르면, �$ N $개의 나라 사이에는 총 �$ M $개의 항공편이 있으며, 각각의 항공편은 출발하는 나라와 도착하는 나라가 정해져있다.

철민이는 즉흥 여행인 만큼 여행 계획을 짜는 대신, 아래 방식으로 여행하겠다는 계획만 세웠다.

• 우선 여행을 시작할 나라를 정한 뒤, 그 나라로 간다.
• 그 뒤로, 현재 있는 나라에서 출발하는 항공편 중 원하는 걸 골라서 탄다.
• 철민이는 하나의 나라를 여러 번 방문할 수 있으며, 하나의 항공편을 여러 번 사용할 수 있다.

위 계획을 본 당신은 철민이가 �$ N $개의 나라를 모두 여행할 수 있을지 걱정이 되기 시작했고, 철민이가 선택하는 시작점과 관계없이 모든 나라를 여행할 수 있을지 미리 확인해보기로 했다.

입력

첫째 줄에 나라의 개수 �$ N $과 항공편의 개수 �$ M $이 주어진다. (1≤�≤200000;$( 1 \le N \le 200\,000; $ 0≤�≤500000)$ 0 \le M \le 500\,000 )$ 

둘째 줄부터 �$ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 �$ v $ �$ w $로 주어진다. 이는 �$ v $번 나라에서 출발해 �$ w $번 나라로 가는 항공편을 의미한다. (1≤�,�≤�;$( 1 \le v, w \le N; $ �≠�)$ v \neq w )$ 

출력

시작점을 어떻게 골라도 모든 나라를 방문할 수 있는 경로가 있다면 Yes를, 아니면 No를 출력한다.

 

어느 나라에서 출발을 하든 모든 나라에 도착할 수 있어야 합니다.

강결합컴포넌트 scc가 단 하나만 있어야 합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, v[200001], s[200001], cnt, num;
vvi scc;
vi adj[200001], st;
int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = ++cnt;
	for (int r : adj[k]) {
		if (!v[r]) {
			parent = min(parent, dfs(r));
		}
		else if (!s[r]) {
			parent = min(parent, v[r]);
		}
	}
	if (v[k] == parent) {
		vi temp; num++;
		while (1) {
			int top = st.back();
			st.pop_back();
			temp.push_back(top);
			s[top] = num;
			if (top == k)break;
		}
		scc.push_back(temp);
	}
	return parent;
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}
	REP(i, N) {
		if (!v[i])dfs(i);
	}
	num==1?cout << "Yes":cout << "No";
}