Cod sursa(job #2203332)

Utilizator MihaiPredoiuMihai Predoiu MihaiPredoiu Data 11 mai 2018 22:23:19
Problema Componente tare conexe Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 2.17 kb
import java.io.*;
import java.util.*;

public class Main {
	public static final int NMAX = 1000005;
	public static final int WHITE = 1;
	public static final int GRAY = 2;
	public static final int BLACK = 3;

	int N;
	int M;
	int c[];
	int k = 0;
	Stack<Integer> S = new Stack<Integer>();

	@SuppressWarnings("unchecked")
	ArrayList<Integer> adj[] = new ArrayList[NMAX];

	@SuppressWarnings("unchecked")
	ArrayList<Integer> adjT[] = new ArrayList[NMAX];

	@SuppressWarnings("unchecked")
	TreeSet<Integer> comps[] = new TreeSet[NMAX];

	public void readInput() {
		Scanner sc;
		try {
			sc = new Scanner(new FileReader("ctc.in"));
			N = sc.nextInt();
			M = sc.nextInt();

			for (int i = 1; i <= N; i++)
				adj[i] = new ArrayList<>();
			for (int i = 1; i <= N; i++)
				adjT[i] = new ArrayList<>();
			for (int i = 1; i <= M; i++) {
				int x, y;
				x = sc.nextInt();
				y = sc.nextInt();
				adj[x].add(y);
				adjT[y].add(x);
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public void explore(int u) {
		c[u] = GRAY;
		for (int v : adj[u]) {
			if (c[v] == WHITE) {
				explore(v);
			}
		}
		c[u] = BLACK;
		S.push(u);
	}

	public void exploreT(int u) {
		c[u] = GRAY;
		comps[k].add(u);
		for (int v : adjT[u]) {
			if (c[v] == WHITE) {
				exploreT(v);
			}
		}
		c[u] = BLACK;
	}

	public void solve() {
		try {
			PrintWriter out = new PrintWriter("ctc.out");

			c = new int[N + 1];

			for (int u = 1; u <= N; u++) {
				c[u] = WHITE;
			}
			for (int u = 1; u <= N; u++) {
				if (c[u] == WHITE) {
					explore(u);
				}
			}
			for (int u = 1; u <= N; u++) {
				c[u] = WHITE;
			}
			while (!S.isEmpty()) {
				int u = S.pop();
				if (c[u] == WHITE) {
					k++;
					comps[k] = new TreeSet<Integer>();
					exploreT(u);
				}
			}

			out.println(k);
			for (int i = 1; i <= k; i++) {
				for (int u : comps[i]) {
					out.print(u + " ");
				}
				out.println();
			}
			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		Main ctc = new Main();
		ctc.readInput();
		ctc.solve();
	}
}