Tunnels

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

/**
 * Created by Florian on 22-Jan-17.
 */
public class Tunnels2 {
	static final int N = 100000;
	static int[] arriving = new int[N];
	static int[] ordered = new int[N];
	static int[] incoming = new int[N];

	public static void main(String args[]) throws IOException {
//		long start = System.nanoTime();
//		Scanner sc = new Scanner(new FileReader("tunnel.txt"));
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
//		BufferedReader bi = new BufferedReader(new InputStreamReader(new FileInputStream("tunnel.txt")));
//		StringTokenizer st = new StringTokenizer(sc.nextLine());
		StringTokenizer st = new StringTokenizer(bi.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<Queue<Integer>> connections = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			connections.add(new LinkedList<>());
		}
//		System.out.println((System.nanoTime() - start) * 1e-6);
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bi.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			incoming[b]++;
			connections.get(a).add(b);
		}
//		System.out.println((System.nanoTime() - start) * 1e-6);
		LinkedList<Integer> noIn = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			if (incoming[i] == 0)
				noIn.add(i);
		}
//		System.out.println((System.nanoTime() - start) * 1e-6);

		int count = 0;
		int node;
		while (!noIn.isEmpty()) {
			node = noIn.poll();
			ordered[count++] = node;
			for (Integer next : connections.get(node)) {
				incoming[next]--;
				if (incoming[next] == 0)
					noIn.add(next);
			}
		}
//		System.out.println((System.nanoTime() - start) * 1e-6);


		int dUsed = 0;
		for (int i = 0; i < n; i++) {
			node = ordered[i];
			dUsed += Math.max(0, connections.get(node).size() - arriving[node]);
			for (Integer next : connections.get(node)) {
				arriving[next]++;
			}
		}
		System.out.println(dUsed);
//		System.out.println((System.nanoTime() - start) * 1e-6);


	}

}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED