Untitled

 avatar
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