Cod sursa(job #2199050)

Utilizator silviucostinMiron Silviu Costin silviucostin Data 26 aprilie 2018 15:31:07
Problema Componente biconexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.5 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.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
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];

		class Edge {
			int x;
			int y;

			Edge(int x, int y) {
				this.x = x;
				this.y = y;
			}

			@Override
			public String toString() {
				return x + " " + y;
			}
		}

		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<>();
				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<HashSet<Integer>> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
								OUTPUT_FILE)));
				pw.printf("%d\n", result.size());
				for (HashSet<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 timp, Deque<Edge> stack, ArrayList<Deque<Integer>> kids, ArrayList<HashSet<Integer>> sol) {
			idx[v] = timp;
			low[v] = timp;
			timp++;
			for (Integer u : adj[v]) {
				stack.push(new Edge(v, u));
				if (idx[u] == 0) {
					kids.get(v - 1).push(u);
					dfsCV(u, idx, low, timp, stack, kids, sol);
					low[v] = Math.min(low[v], low[u]);
				} else {
					low[v] = Math.min(low[v], idx[u]);
				}
			}
			if (v == 1) {
				if (kids.get(v - 1).size() >= 2) {
					for (Integer k : kids.get(v - 1)) {
						HashSet<Integer> aux = new HashSet<>();
						Edge edge = new Edge(-1, -1);
						while (edge.x != v || edge.y != k) {
							edge = stack.remove();
							aux.add(edge.x);
							aux.add(edge.y);
						}
						sol.add(aux);
					}
				}
			} else {
				for (Integer u : kids.get(v - 1)) {
					if (low[u] >= idx[v]) {
						HashSet<Integer> aux = new HashSet<>();
						Edge edge = new Edge(-1, -1);
						while (edge.x != v || edge.y != u) {
							edge = stack.remove();
							aux.add(edge.x);
							aux.add(edge.y);
						}
						sol.add(aux);
					}
				}
			}
		}

		private ArrayList<HashSet<Integer>> getResult() {
			// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
			// de adiacenta in adj.
			ArrayList<HashSet<Integer>> sol = new ArrayList<>();
			int timp = 1;
			int idx[] = new int[n + 1];
			int low[] = new int[n + 1];
			Deque<Edge> stack = new ArrayDeque<Edge>();
			ArrayList<Deque<Integer>> kids = new ArrayList<>();
			for (int v = 1; v <= n; v++) {
				kids.add(new ArrayDeque<Integer>());
			}
			for (int v = 1; v <= n; v++) {
				if (idx[v] == 0) {
					dfsCV(v, idx, low, timp, stack, kids, sol);
				}
			}
			return sol;
		}

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

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