Cod sursa(job #1748820)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 august 2016 22:32:49
Problema Componente biconexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 7.88 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new FileInputStream("biconex.in"));

        int N = in.nextInt();
        int M = in.nextInt();

        Graph G = new Graph(N);

        for (int i = 0; i < M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();

            G.addEdge(x, y);
            G.addEdge(y, x);
        }

        BiconnectedComponents BC = new BiconnectedComponents(G);
        int[][] components = BC.computeBiconnectedComponents();

        PrintWriter out = new PrintWriter(new FileOutputStream("biconex.out"));

        out.println(components.length);

        for (int i = 0; i < components.length; i++) {
            for (int j = 0; j < components[i].length; j++) {
                out.printf("%d ", components[i][j]);
            }
            out.println();
        }

        in.close();
        out.close();
    }

    static class Graph{
        private static class Edge{
            int node;
            int next;

            Edge(int node, int next){
                this.node = node;
                this.next = next;
            }
        }

        final static int NIL = -1;
        private int[] head;
        private int[] degree;
        private ArrayList<Edge> graph;

        private int N;
        private int counter;

        Graph(int N){
            initialize(N);
        }

        public int getN() {
            return N;
        }

        private void initialize(final int N){
            head = new int[N];
            degree = new int[N];
            graph = new ArrayList<>();

            this.N = N;
            this.counter = 0;

            Arrays.fill(head, NIL);
            Arrays.fill(degree, 0);
        }

        void addEdge(int x, int y){
            if (!(1 <= x && x <= N)) throw new AssertionError();
            x--; y--;
            graph.add(new Edge(y, head[x]));
            head[x] = counter++;
            degree[x]++;
        }

        int getHead(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();
            node--;
            return head[node];
        }

        int getNext(int p){
            if (!(0 <= p && p < counter)) throw new AssertionError();
            return graph.get(p).next;
        }

        int getNeighbour(int p){
            if (!(0 <= p && p < counter)) throw new AssertionError();
            return graph.get(p).node + 1;
        }

        boolean isEmpty(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();
            node--;
            return head[node] == NIL;
        }

        int size(int node){
            assert 1 <= node && node <= N;
            node--;
            return degree[node];
        }

        Graph transpose(){
            Graph GT = new Graph(N);

            for (int i = 1; i <= N; i++) {
                for (int son : getNeighbours(i))
                    GT.addEdge(son, i);
            }

            return GT;
        }

        List<Integer> getNeighbours(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();

            List<Integer> list = new ArrayList<>();

            for (int p = head[node - 1]; p != NIL; p = graph.get(p).next) {
                list.add(graph.get(p).node + 1);
            }

            return list;
        }
    }

    static class Pair implements Comparable<Pair>{
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair o) {
            int cmp1 = Integer.compare(first, o.first);

            if (cmp1 != 0)
                return cmp1;
            else
                return Integer.compare(second, o.second);
        }
    }

    static class BiconnectedComponents {
        private final Graph G;
        private final int N;

        private final int[] lowIndex, dfn;
        private List<Pair> stack;

        private final ArrayList<ArrayList<Integer>> components;
        private int numberOfBCs;
        private final boolean[] articulationPoints;
        private final ArrayList<Pair> bridges;

        BiconnectedComponents(Graph graph){
            this.G = graph;
            this.N = G.getN();

            lowIndex = new int[N + 1];
            dfn = new int[N + 1];
            stack = new LinkedList<>();

            articulationPoints = new boolean[N + 1];
            components = new ArrayList<>();
            bridges = new ArrayList<>();
        }

        private void dfs(int node, int root, int number){
            lowIndex[node] = dfn[node] = number;
            int numberSons = 0;
            boolean isArticulationPoint = false;

            for (int p = G.getHead(node); p != Graph.NIL; p = G.getNext(p)){
                int son = G.getNeighbour(p);

                if (dfn[son] == -1){
                    numberSons++;
                    stack.add(new Pair(node, son));
                    dfs(son, root, number + 1);

                    lowIndex[node] = Math.min(lowIndex[node], lowIndex[son]);

                    if (lowIndex[son] >= dfn[node]) { // node is an articulation point
                        biconex(node, son);
                        isArticulationPoint = true;
                    }

                    if (lowIndex[son] > dfn[node]){
                        // (node,son) is a bridge
                        bridges.add(new Pair(Math.min(node, son), Math.max(node, son)));
                    }
                }
                else
                    lowIndex[node] = Math.min(lowIndex[node], dfn[son]);
            }

            if (isArticulationPoint || (node == root && numberSons > 1)){
                articulationPoints[node] = true;
            }
        }

        private void biconex(int node, int son){
            components.add(new ArrayList<Integer>());
            Pair p = new Pair(node, son);
            Pair q;

            do {
                q = stack.get(stack.size() - 1);
                stack.remove(stack.size() - 1);

                components.get(numberOfBCs).addAll(Arrays.asList(q.first, q.second));

            } while (p.compareTo(q) != 0);

            numberOfBCs++;
        }

        int[][] computeBiconnectedComponents(){
            numberOfBCs = 0;
            components.clear();
            stack.clear();
            bridges.clear();

            Arrays.fill(dfn, -1);
            Arrays.fill(lowIndex, -1);
            Arrays.fill(articulationPoints, false);

            for (int i = 1; i <= N; i++) {
                if (dfn[i] == -1) {
                    dfs(i, i, 0);
                    break;
                }
            }

            int[][] comps = new int[numberOfBCs][];

            for (int i = 0; i < numberOfBCs; i++) {

                Set<Integer> hashSet = new HashSet<>();

                for (int x : components.get(i)) {
                    hashSet.add(x);
                }

                ArrayList<Integer> list = new ArrayList<>(hashSet);
                list.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return Integer.compare(o1, o2);
                    }
                });

                comps[i] = new int[list.size()];

                for (int j = 0; j < list.size(); j++) {
                    comps[i][j] = list.get(j);
                }
            }

            return comps;
        }

        boolean[] getArticulationPoints(){
            return articulationPoints;
        }

        Pair[] getBridges(){
            Pair[] bridge = new Pair[bridges.size()];

            for (int i = 0; i < bridge.length; i++) {
                bridge[i] = bridges.get(i);
            }

            return bridge;
        }
    }

}