[Java] Runtime: 4 ms, faster than 99.21%
Runtime: 4 ms, faster than 99.21%\uFF0CMemory Usage: 53.9 MB, less than 100.00% of Java online submissions\n\n\npublic int minReorder(int n, int[][] roads) {\n\
**Runtime: 4 ms, faster than 99.21%\uFF0CMemory Usage: 53.9 MB, less than 100.00% of Java online submissions**\n\n```\npublic int minReorder(int n, int[][] roads) {\n\tint res = 0;\n\t//find the first i make roads[i][0] =0 or roads[i][1] = 0, and swap roads[i] and roads[0]\n\tupdateZeroCityInHead(roads);\n\tint sortedIndex = 0, moveIndex = 1;\n\t//record the road\n\tint[] record = new int[n];\n\trecord[roads[0][0]] = 1;\n\trecord[roads[0][1]] = 1;\n\n\t//sort the roads array,  to make the roads[i][0] or roads[i][1] (i>0)is exist in {roads[0][0] roads[0][1] .... roads[i-1][0] roads[i-1][1]}\u3002\n\twhile (sortedIndex + 1 >= n) {\n\t\tboolean swap = false;\n\t\tif (record[roads[moveIndex][0]] == 1\n\t\t\t\t|| record[roads[moveIndex][1]] == 1) {\n\t\t\trecord[roads[moveIndex][0]] = 1;\n\t\t\trecord[roads[moveIndex][1]] = 1;\n\t\t\tsortedIndex++;\n\t\t\tif (sortedIndex != moveIndex) {\n\t\t\t\tswap(roads, sortedIndex, moveIndex);\n\t\t\t\tswap = true;\n\t\t\t}\n\t\t}\n\t\tif (!swap) {\n\t\t\tmoveIndex++;\n\t\t}\n\t\tif (moveIndex >= n) {\n\t\t\tmoveIndex = sortedIndex + 1;\n\t\t}\n\t}\n\t//because roads[i][0] or roads[i][1] (i>0)is exist in S = {roads[0][0] roads[0][1] .... roads[i-1][0] roads[i-1][1]}, \n\t//if  roads[i][1] is not in S, so we should change it, let res++;\n\tint[] t = new int[n];\n\tt[0] = 1;\n\tfor (int[] c : roads) {\n\t\tif (t[c[1]] == 0) {\n\t\t\tres++;\n\t\t}\n\t\tt[c[0]] = 1;\n\t\tt[c[1]] = 1;\n\t}\n\treturn res;\n}\n\n\n/**\n * find the first i make roads[i][0] =0 or roads[i][1] = 0, and swap roads[i] and roads[0]\n */\nprivate void updateZeroCityInHead(int[][] t) {\n\tint zeroIndex = -1;\n\tfor (int i = 0; i < t.length; i++) {\n\t\tif (t[i][0] == 0 || t[i][1] == 0) {\n\t\t\tzeroIndex = i;\n\t\t\tbreak;\n\t\t}\n\t}\n\tif (zeroIndex == -1) {\n\t\tthrow new IllegalArgumentException("connections is illegal!");\n\t}\n\tif (zeroIndex != 0) {\n\t\tswap(t, 0, zeroIndex);\n\t}\n}\n\nprivate void swap(int[][] t, int src, int des) {\n\tint[] f = t[src];\n\tt[src] = t[des];\n\tt[des] = f;\n}\n```\n\nIf the test case satisfies **roads[i][0] or roads[i][1] (i>0)is exist in S = {roads[0][0] roads[0][1] .... roads[i-1][0] roads[i-1][1]}**,\n**not like:**\n```\n3\n[[1,2],[2,0]]\n6\n[[2,3],[3,1],[1,0],[4,0],[4,5]]\n```\n**just use the following code , it can pass all test cases of leetcode, otherwise sort it first.**\n\n```\npublic int minReorder(int n, int[][] roads) {\n\tint res = 0;\n\tint[] t = new int[n];\n\tt[0] = 1;\n\tfor (int[] c : roads) {\n\t\tif (t[c[1]] == 0) {\n\t\t\tres++;\n\t\t}\n\t\tt[c[0]] = 1;\n\t\tt[c[1]] = 1;\n\t}\n\treturn res;\n}\n```\n
['Java']