핵심 아이디어

<aside> 💡

비용이 양의 정수 이므로 정점 $1$에서 $i$로 갈 때 $1\le k \le i$인 정점 $k$를 거처야만 $i$에 도달할 수 있다면 절대로 조건을 만족 하는 가중치를 설정할 수 없다.

</aside>

예시) 1-3-2 인 그래프는 1에서 2로 가는 비용이 1에서 3으로 가는 비용보다 절대 작을 수 없다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n, m;
vector<int> adj[200'001];

bool v[200'001];

void dfs(int cur)
{
    v[cur] = true;

    for(int nxt: adj[cur]){
        if(v[nxt]) continue;
        dfs(nxt);
    }
}

signed main()
{
    FASTIO;
    cin >> n >> m;
    for(int i = 0; i<m; i++){
        int x, y;
        cin >> x >> y;
        adj[min(x, y)].push_back(max(x, y));
    }

    dfs(1);

    for(int i = 1; i<=n; i++){
        if(v[i]) continue;
        cout << "NO\\n";
        return 0;
    }

    cout << "YES\\n";
    return 0;
}