Cod sursa(job #2609747)

Utilizator danserboiSerboi Florea-Dan danserboi Data 3 mai 2020 13:43:10
Problema Componente biconexe Scor 10
Compilator java Status done
Runda Arhiva educationala Marime 4.82 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.Stack;
import java.util.TreeSet;
import java.util.ArrayList;

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;
			public Edge(int x, int y) {
				super();
				this.x = x;
				this.y = y;
			}
			@Override
			public String toString() {
				return "Edge [x=" + x + ", y=" + y + "]";
			}
			
		}
		
		private void readInput() {
			try {
				BufferedReader br = new BufferedReader(new FileReader(
						INPUT_FILE));
				String line = br.readLine();
				String[] fields = line.split(" ");
				n = Integer.parseInt(fields[0]);
				m = Integer.parseInt(fields[1]);
				
				for (int i = 1; i <= n; i++) {
					adj[i] = new ArrayList<>();
				}
				for (int i = 1; i <= m; i++) {
					int x, y;
					line = br.readLine();
					fields = line.split(" ");
					x = Integer.parseInt(fields[0]);
					y = Integer.parseInt(fields[1]);
					adj[x].add(y);
				}
				br.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void writeOutput(ArrayList<TreeSet<Integer>> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
								OUTPUT_FILE)));
				
				pw.printf("%d\n", result.size());
				for(int i = 0; i <= result.size() - 1; i++) {
					TreeSet<Integer> comp = result.get(i);
					while (comp.size() > 1) {
						int n = comp.pollFirst();
						pw.printf("%d ", n);
					}
					if(comp.size() == 1) {
						int n = comp.pollFirst();
						pw.printf("%d", n);
					}
					pw.println();
				}
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private ArrayList<TreeSet<Integer>> getResult() {
			ArrayList<TreeSet<Integer>> sol = new ArrayList<>();
			int timp = 0;
			int idx[] = new int[n+1];
			int low[] = new int[n+1];
			int parent[] = new int[n+1];
			for(int i = 0; i <= n; i++) {
				idx[i] = -1;
				low[i] = -1;
			}
			Stack<Edge> stack = new Stack<Edge>();
			for(int v = 1; v <= n; v++) {
				if(idx[v] == -1) {
					timp = dfsBC(sol, stack, timp, parent, low, idx, v);
					TreeSet<Integer> sortedSet = new TreeSet<Integer>();
					while(!stack.isEmpty()) {
						Edge e = stack.pop();
						sortedSet.add(e.x);
						sortedSet.add(e.y);
					}
					sol.add(sortedSet);
				}
			}
			return sol;
		}

		public int dfsBC(ArrayList<TreeSet<Integer>> sol, Stack<Edge> stack, int timp, int[] parent, int[] low, int[] idx, int v) {
			idx[v] = timp;
			low[v] = timp;
			timp++;
			ArrayList<Integer> childs = new ArrayList<Integer>();
			for(int i = 0; i <= adj[v].size() - 1; i++) {
				int u = adj[v].get(i);
				// daca u nu este parintele lui v
				if(parent[v] != u) {
					// daca nodul este nevizitat
					if(idx[u] == -1) {
						stack.push(new Edge(v, u));
						childs.add(u);
						parent[u] = v;
						timp = dfsBC(sol, stack, timp, parent, low, idx, u);
						low[v] = Integer.min(low[v], low[u]);
					}
					else {
						stack.push(new Edge(v, u));
						// nodul u este descoperit, verificam daca gasim o scurtatura catre un stramos
						low[v] = Integer.min(low[v], idx[u]);
					}
				}
			}
			// v este punct de articulatie daca:
			if(parent[v] == 0) {				
				// v este radacina arborelui de adancime si v are doi sau mai multi copii 
				if(childs.size() >= 2) {
					TreeSet<Integer> sortedSet = new TreeSet<Integer>();
					while(stack.peek().x != v) {
						Edge e = stack.pop();
						sortedSet.add(e.x);
						sortedSet.add(e.y);
					}
					Edge e = stack.pop();
					sortedSet.add(e.x);
					sortedSet.add(e.y);
					sol.add(sortedSet);
				}
			} else {
				// v nu este radacina arborelui de adancime si are un copil u in arbore, 
				// astfel incat niciun nod din subarborele dominat de u 
				// nu este conectat cu un stramos al lui v printr-o muchie inapoi 
				// (copii lui nu pot ajunge pe alta cale pe un nivel superior 
				// in arborele de adancime)
				int ok = 0;
				for(int i = 0; i <= childs.size() - 1; i++) {
					int u = childs.get(i);
					if(low[u] >= idx[v]) {
						ok = 1;
						break;
					}
				}
				if(ok == 1) {
					TreeSet<Integer> sortedSet = new TreeSet<Integer>();
					while(stack.peek().x != v) {
						Edge e = stack.pop();
						sortedSet.add(e.x);
						sortedSet.add(e.y);
					}
					Edge e = stack.pop();
					sortedSet.add(e.x);
					sortedSet.add(e.y);
					sol.add(sortedSet);
				}
			}
			return timp;
		}
		
		public void solve() {
			readInput();
			writeOutput(getResult());
		}
	}

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