Cod sursa(job #2405960)

Utilizator QQQ1911Vodita Stefan QQQ1911 Data 15 aprilie 2019 11:21:06
Problema Componente biconexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.68 kb
package bonus;

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.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

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];
		
		int time;
		int idx[];
		int low[];
		List<Edge> s = new ArrayList<>();
		ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
		
		class Edge {
			int x;
			int y;
			
			public Edge(int x, int y) {
				this.x = x;
				this.y = 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<ArrayList<Integer>> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
								OUTPUT_FILE)));
				pw.printf("%d\n", result.size());
				for (ArrayList<Integer> ctc : result) {
					for (int nod : ctc) {
						pw.printf("%d ", nod);
					}
					pw.printf("\n");
				}
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		
		public void push(Edge e) {
			s.add(e);
		}
		
		public Edge pop() {
			return s.remove(s.size() - 1);
		}
		
		public int min(int x, int y) {
			return x < y ? x : y;
		}
		
		public boolean isRoot(int v) {
			return v == 1;
		}
		
		public ArrayList<Integer> generateNewSol(Edge edge) {
			System.out.println("Generete with stack size: " + s.size());
			Set<Integer> set = new HashSet<Integer>(); 
			ArrayList<Integer> newSol;
			while (!s.isEmpty()) {
				Edge e = pop();
				set.add(e.x);
				set.add(e.y);
				if (e.x == edge.x && e.y == edge.y) {
					break;
				}
			}
			newSol = new ArrayList<>(set);
			System.out.println("New sol size: " + newSol.size());
			return newSol;
		}
		
		public void cutVertex() {
			time = 0;
			s = new ArrayList<>();
			for (int v = 1; v <= n; ++v) {
				if (idx[v] == -1) {
					dfsCV(v, 0);
				}
			}
		}
		
		public void dfsCV(int v, int parent) {
			idx[v] = time;
			low[v] = time++;
			//push(v);
			List<Integer> children = new ArrayList<>();
			for (int u : adj[v]) {
				if (u == parent) {
					continue;
				}
				if (idx[u] == -1) {
					push(new Edge(v, u));
					System.out.println(v + " " + u);
					children.add(u);
					dfsCV(u, v);
					low[v] = min(low[v], low[u]);
					if (low[u] >= idx[v]) {
						System.out.println("New biconex " + v + " " + u);
						sol.add(generateNewSol(new Edge(v, u)));
					}
				} else {
					low[v] = min(low[v], idx[u]);
				} 
				System.out.println(v + " " + idx[v] + " " + u + " " + low[u]);
				
			}
		}

		private ArrayList<ArrayList<Integer>> getResult() {
			// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
			// de adiacenta in adj.
			low = new int[n + 1];
			idx = new int[n + 1];
			for (int i = 0; i <= n; ++i) {
				idx[i] = -1;
			}
			
			cutVertex();
			
			return sol;
		}

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

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