DataStructuresinJava/kosaraju.java at master · prashant4nov/DataStructuresinJava · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.*;
import static java.lang.Math.min;
import static java.lang.Math.max;
import static java.lang.Math.toIntExact;

public class Main {
    private static Scanner input;

    static int N = 20010;

    static boolean marked[];
    static int comp[] = new int[N];
    static int comps;
    static int t,n,m,u,v;
    static Stack<Integer> s = new Stack<Integer>();
    static List<Integer>[] g;
    static List<Integer>[] gi;

    static void dfs(int v) {
        if(marked[v]) return;
        marked[v] = true;
        for(int i = 0; i < g[v].size(); i++) {
            dfs(g[v].get(i));
        }
        s.push(v);
    }

    static void dfs2(int v, int c) {
        if(marked[v]) return;

        marked[v] = true;
        comp[v] = c;
        for(int i = 0; i < gi[v].size(); i++) {
            dfs2(gi[v].get(i), c);
        }
    }


    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws java.lang.Exception {

        //try {
            input = new Scanner(System.in);
            int t, n, m, x, y;

            t = toIntExact(input.nextLong());

            while(t-- > 0) {
                n = toIntExact(input.nextLong());
                m = toIntExact(input.nextLong());

                g = new ArrayList[n];
                gi = new ArrayList[n];

                for(int i = 0; i < n; i++) {
                    g[i] = new ArrayList<Integer>();
                    gi[i] = new ArrayList<Integer>();
                }

                for(int i = 0; i < m; i++) {
                    u = toIntExact(input.nextLong());
                    v = toIntExact(input.nextLong());
                    u--; v--;
                    g[u].add(v);
                    gi[v].add(u);
                }

                marked = new boolean[N];
                for(int i = 0; i < n; i++) {
                    dfs(i);
                }

                marked = new boolean[N];

                comps = 0;

                while(!s.isEmpty()) {
                    int v = s.pop();
                    if(!marked[v]) {
                        dfs2(v, comps++);
                    }
                }

                boolean in[] = new boolean[comps];
                boolean out[] = new boolean[comps];

                for(int i = 0; i < comps; i++) {
                    for(int j = 0; j < g[i].size(); j++) {
                        u = i; v = g[i].get(j);
                        if(comp[u] != comp[v]) {
                            out[comp[u]]=true;
                            in[comp[v]]=true;
                        }
                    }
                }

                int need_in = 0, need_out = 0;
                for (int i=0;i<comps;i++){
                    if (!in[i]) need_in++;
                    if (!out[i]) need_out++;
                }

                if(comps == 1) System.out.println(0);
                else {
                    System.out.println(max(need_in, need_out));
                }

            }

        //} catch (Exception e) {
            //System.out.println(e.getMessage());
        //}
            }
}