Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Course Schedule

Medium · Graphs · Asked at Amazon, Google, Microsoft, Meta, Uber

There are n courses (1..n). A pair a b means you must finish course b before course a. Print YES if it is possible to finish all courses, otherwise NO.

Input

First line: n m. Next m lines: a b.

Output

YES or NO.

Constraints

It is possible exactly when the directed graph has no cycle — Kahn's algorithm (topological sort with indegrees).

Example 1

Input

2 1
2 1

Output

YES

Example 2

Input

2 2
2 1
1 2

Output

NO

Hints

  1. Draw an edge b → a for "b before a". All courses can be finished exactly when this directed graph has no cycle.
  2. Kahn's algorithm: repeatedly take a course with indegree 0. If you manage to take all n courses, there is no cycle.

Approach

Build edges b → a and count each course's indegree (number of prerequisites). Push all courses with indegree 0 into a queue. Pop a course, count it as taken, and decrease its dependents' indegrees, pushing any that drop to 0. If the number taken is n, the answer is YES. Courses on a cycle never reach indegree 0, so a cycle leaves the count below n.

Complexity: O(n + m) time · O(n + m) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[b].push_back(a);  // b must come before a
        indeg[a]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        taken++;
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    cout << (taken == n ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
    a, b = data[2 + 2 * i], data[3 + 2 * i]
    adj[b].append(a)  # b must come before a
    indeg[a] += 1

q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
taken = 0
while q:
    u = q.popleft()
    taken += 1
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
print("YES" if taken == n else "NO")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            adj.get(b).add(a);  // b must come before a
            indeg[a]++;
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++)
            if (indeg[i] == 0) q.add(i);
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj.get(u))
                if (--indeg[v] == 0) q.add(v);
        }
        System.out.println(taken == n ? "YES" : "NO");
    }
}

Solve Course Schedule online · All practice problems