Untitled
unknown
plain_text
a year ago
2.0 kB
5
Indexable
public class Solution { static int[][] g, c; static int[] l, path, color, par; static int N, E, number, index; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("src/dfs/findcycle/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); E = sc.nextInt(); g = new int[N][N]; c = new int[N][N]; color = new int[N]; par = new int[N]; l = new int[N]; path = new int[N]; number = 0; index = 0; for (int i = 0; i < E; i++) { int u = sc.nextInt(); int v = sc.nextInt(); addEdge(u, v); } dfs_cycle(1, 0); printCycles(); } } static void dfs_cycle(int u, int p) { if (color[u] == 2) { return; } if (color[u] == 1) { int cur = p; c[number][l[number]++] = cur; while (cur != u) { cur = par[cur]; c[number][l[number]++] = cur; } number++; return; } par[u] = p; color[u] = 1; path[index++] = u; for (int v = 0; v < N; v++) { if (g[u][v] == 1) { if (v == par[u]) { continue; } dfs_cycle(v, u); } } color[u] = 2; index--; } static void addEdge(int u, int v) { g[u][v] = 1; // do thi vo huong // g[v][u] = 1; } static void printCycles() { if (number == 0) { System.out.println(-1); // No cycle return; } System.out.println("Total: " + number); for (int i = 0; i < number; i++) { int[] arr = new int[l[i]]; for (int j = 0; j < l[i]; j++) { System.out.printf("%d ", c[i][j]); // arr[j] = c[i][j]; } // sortDecs(arr); System.out.println(); } } // static void sortDecs(int[] arr) { // for (int j = 0; j < arr.length; j++) { // for (int jj = j + 1; jj < arr.length; jj++) { // if (arr[j] < arr[jj]) { // int t = arr[j]; // arr[j] = arr[jj]; // arr[jj] = t; // } // } // System.out.printf("%d ", arr[j]); // } // } }
Editor is loading...
Leave a Comment