Cod sursa(job #2602418)

Utilizator ShayTeodor Matei Shay Data 16 aprilie 2020 21:03:47
Problema Componente biconexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.51 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.*;

public class Biconex {
	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; 
		public static int time = 0;
		int n;
		int m;
		int [] disc;
		int [] low;
		@SuppressWarnings("unchecked")
		ArrayList<Integer> adj[] = new ArrayList[NMAX];
		ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
		Stack<Integer> st = new Stack<>();
		private void readInput() {
			try {
				Scanner sc = new Scanner(new BufferedReader(new FileReader(
						INPUT_FILE)));
				n = sc.nextInt();
				m = sc.nextInt();
				disc = new int[n + 1];
				low = new int[n + 1];
				Arrays.fill(disc, -1);

				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<ArrayList<Integer>> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
								OUTPUT_FILE)));
				pw.printf("%d\n", result.size());
				for (ArrayList<Integer> bic : result) {
					for (int nod : bic) {
						pw.printf("%d ", nod);
					}
					pw.printf("\n");
				}
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void dfs(int src, int dad) {
			disc[src] = low[src] = disc[dad] + 1;
			st.push(src);
			for (Integer it : adj[src]) {
				if (disc[it] == -1) {
					dfs(it, src);
					low[src] = Math.min(low[src], low[it]);
					if (low[it] >= disc[src]) {
						ArrayList<Integer> biconnectedComp = new ArrayList();
						int node;
						do {
							biconnectedComp.add(node = st.peek());
							st.pop();
						} while(it != node);
						
						biconnectedComp.add(src);
						sol.add(biconnectedComp);
					}
				} else if (it != dad){
					low[src] = Math.min(low[src], disc[it]);
				}
			}
		}

		private ArrayList<ArrayList<Integer>> getResult() {
			// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
			// de adiacenta in adj.
			
			
			dfs(1, 0);
			return sol;
		}

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

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