Table of Contents

ExplanationImplementation

Explanation

We can use the games to construct a directed graph. If aa wins against bb then we can construct an edge from bb to aa. Since the bounds of NN and MM are small, we can start a DFS from every vertex. If we reach that vertex again, then we can mark that vertex as “cyclic” and count said vertex in the result.

Implementation

O(N2+M)\mathcal{O}(N^2 + M) time

C++

#include <iostream>
#include <vector>
using namespace std;


const int MAX_N = 20;
vector<vector<int>> adj(MAX_N);
bool vis[MAX_N], cyclic[MAX_N];


int original_node;

Python

n, m = map(int, input().split())


adj = [[] for _ in range(n)]
vis, cyclic = [False for _ in range(n)], [False for _ in range(n)]
original_node = -1




def dfs(node):
	if vis[node]:
		return

Java

import java.io.*;
import java.util.*;


public class Rank {
	static Map<Integer, HashSet<Integer>> graph = new HashMap<>();
	static int ans = 0;
	static Set<Integer> visited = new HashSet<>();
	static boolean cyclic = false;


	public static void main(String[] args) throws IOException {

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum