Cod sursa(job #2413015)

Utilizator silviuNssNastasescu George-Silviu silviuNss Data 22 aprilie 2019 19:43:07
Problema Componente biconexe Scor 20
Compilator java Status done
Runda Arhiva educationala Marime 6.25 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.Scanner; 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Stack;

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;
                int timp;

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

                class Edge {
			int x;
			int 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);
			}
		}
                
                
		private ArrayList<ArrayList<Integer>> getResult() {
                    
                        System.out.println("n = " + n + " si m = " + m);
			ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
			timp = 0;
                        Stack<Edge> s = new Stack<>();
                        
                        int[] idx = new int[n + 1];
                        int[] low = new int[n + 1];
                        
                        for(int i = 1; i <= n; i++){
                            idx[i] = NMAX;
                            low[i] = NMAX;
                        }
                        
                        for(int i = 1; i <= n; i++) {
                            if(idx[i] == NMAX) {
                                dfsCV(i, idx, low, true, sol, s);
                            }
                        }
                        
			return sol;
		}
                
                private void dfsCV(int start, int[] idx, int[] low, boolean rad, ArrayList<ArrayList<Integer>> sol, Stack<Edge> s){
                    idx[start] = timp;
                    low[start] = timp;
                    timp++;
                    HashSet<Integer> copii = new HashSet<>();
                    
                    for(int neigh : adj[start]){
                        if(idx[neigh] == NMAX){
                            Edge edge = new Edge();
                            edge.x = start;
                            edge.y = neigh;
                            s.push(edge);
                            copii.add(neigh);
                            dfsCV(neigh, idx, low, false, sol, s);
                            low[start] = Math.min(low[start], low[neigh]);
                        }
                        else {
                            if(rad)
                                copii.add(neigh);
                            low[start] = Math.min(low[start], idx[neigh]);
                        }
                    }
                    
                    if(rad) {
                        System.out.println("Pentru start = " + start + " avem nr_copii = " + copii.size());
                        if(copii.size() >= 2) {
                            for(int i = 1; i <= copii.size(); i++) {
                                while(!s.isEmpty()) {
                                    Edge ed;
                                    HashSet<Integer> nodes = new HashSet<>();
                                    do {
                                        ed = s.pop();
                                        System.out.println("ed.x = " + ed.x + " si ed.y = " + ed.y);
                                        nodes.add(ed.x);
                                        nodes.add(ed.y);
                                    }
                                    while(ed.x != start);
                                    ArrayList<Integer> ar = new ArrayList<>(nodes);
                                    Collections.sort(ar);
                                    sol.add(ar);

                                }
                            }
                        }
                    }
                    else {
                        for(int neigh : copii){
                            if(low[neigh] >= idx[start]) {
                                Edge ed, edge = new Edge();
                                edge.x = start;
                                edge.y = neigh;
                                HashSet<Integer> nodes = new HashSet<>();
                                System.out.println("Pentru start = " + start + " si neigh = " + neigh + " avem:");
                                
                                do {
                                    ed = s.pop();
                                    System.out.println("ed.x = " + ed.x + " si ed.y = " + ed.y);
                                    nodes.add(ed.x);
                                    nodes.add(ed.y);
                                }
                                while(ed.x != edge.x && ed.y != edge.y);
                                
                                ArrayList<Integer> ar = new ArrayList<>(nodes);
                                Collections.sort(ar);
                                sol.add(ar);
                                break;
                            }
                        }
                    }
                    
                }

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

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