Cod sursa(job #2203929)

Utilizator silviucostinMiron Silviu Costin silviucostin Data 13 mai 2018 18:35:36
Problema Componente biconexe Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 2.74 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static class Task {
		public static final String INPUT_FILE = "biconex.in";
		public static final String OUTPUT_FILE = "biconex.out";
		public static final int NMAX = 100005; // 10^5

		int n;
		int m;

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

		private void readInput() {
			try {
				Scanner sc = new Scanner(new BufferedReader(new FileReader(
								INPUT_FILE)));
				n = sc.nextInt();
				m = sc.nextInt();

				for (int i = 1; i <= n; i++)
					adj[i] = new ArrayList<Integer>();
				for (int i = 1; i <= m; i++) {
					int x, y;
					x = sc.nextInt();
					y = sc.nextInt();
					adj[x].add(y);
					adj[y].add(x);
				}
				sc.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void writeOutput(ArrayList<Deque<Integer>> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
								OUTPUT_FILE)));
				pw.printf("%d\n", result.size());
				for (Deque<Integer> ctc : result) {
					for (int nod : ctc) {
						pw.printf("%d ", nod);
					}
					pw.printf("\n");
				}
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void dfsCV(int v, int[] idx, int[] low, int time, ArrayList<Deque<Integer>> sol, int parent, Deque<Integer> stack) {
			idx[v] = time;
			low[v] = time;
			time++;
			stack.push(v);
			for (Integer u : adj[v]) {
				if (u == parent)
					continue;
				if (idx[u] == 0) {
					dfsCV(u, idx, low, time, sol, v, stack);
					if (low[u] >= idx[v]) {
						Deque<Integer> aux = new LinkedList<Integer>();
						int x = -1;
						while (!stack.isEmpty() && x != u) {
							 x = stack.pop();
							aux.add(x);
						}
						aux.push(v);
						sol.add(aux);
					}
					low[v] = Math.min(low[v], low[u]);
				} else {
					low[v] = Math.min(low[v], idx[u]);
				}
			}
		}

		private ArrayList<Deque<Integer>> getResult() {
			// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
			// de adiacenta in adj.
			ArrayList<Deque<Integer>> sol = new ArrayList<Deque<Integer>>();
			Deque<Integer> stack = new LinkedList<Integer>();
			int time = 1;
			int idx[] = new int[n + 1];
			int low[] = new int[n + 1];

			for (int v = 1; v <= n; v++) {
				if (idx[v] == 0) {
					dfsCV(v, idx, low, time, sol, 0, stack);
				}
			}
			return sol;
		}

		public void solve() {
			readInput();
			writeOutput(getResult());
		}
	}

	public static void main(String[] args) {
		new Task().solve();
	}
}