E11

public class Hrana implements Comparable<Hrana> {

        int vrchol1;
        int vrchol2;
        double ohodnotenie;

        public Hrana(int vrchol1, int vrchol2, double ohodnotenie) {
                this.vrchol1 = vrchol1;
                this.vrchol2 = vrchol2;
                this.ohodnotenie = ohodnotenie;
        }

        @Override
        public String toString() {
                return "[" + vrchol1 + " - " + vrchol2 + " : " + ohodnotenie + "]";
        }

        public int getVrchol1() {
                return vrchol1;
        }

        public int getVrchol2() {
                return vrchol2;
        }

        public double getOhodnotenie() {
                return ohodnotenie;
        }

        @Override
        public int compareTo(Hrana o) {
                return (int) Math.signum(ohodnotenie - o.ohodnotenie);
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                long temp;
                temp = Double.doubleToLongBits(ohodnotenie);
                result = prime * result + (int) (temp ^ (temp >>> 32));
                result = prime * result + vrchol1;
                result = prime * result + vrchol2;
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Hrana other = (Hrana) obj;

                return ((vrchol1 == other.vrchol1 && vrchol2 == other.vrchol2) ||
                                (vrchol1 == other.vrchol2 && vrchol2 == other.vrchol1));
        }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Mst {

        public static final double NIE_JE_HRANA = Double.POSITIVE_INFINITY;

        public static List<Hrana> dijkstraPrim(double[][] ms) {
                return dijkstraPrim(ms, 0);
        }

        public static List<Hrana> dijkstraPrim(double[][] ms, int s) {
                double[] hodnoty = new double[ms.length];
                boolean[] vybavene = new boolean[ms.length];
                int[] predchodcovia = new int[ms.length];
                int pocetVybavenych = 1;
                int vrchol = s;

                Arrays.fill(vybavene, false);
                vybavene[s] = true;
                predchodcovia[s] = -1;

                for (int i = 0; i < ms.length; i++)
                        hodnoty[i] = (i == s) ? 0 : Double.POSITIVE_INFINITY;

                List<Hrana> mst = new ArrayList<Hrana>(ms.length - 1);
                while (pocetVybavenych < ms.length) {
                        // hladam susedov vrcholu
                        double minHodnota = Double.POSITIVE_INFINITY;
                        int minIdx = -1;
                        for (int i = 0; i < ms.length; i++) {
                                if (ms[vrchol][i] == NIE_JE_HRANA || vybavene[i])
                                        continue;

                                if (ms[vrchol][i] < hodnoty[i]) {
                                        hodnoty[i] = ms[vrchol][i];
                                        predchodcovia[i] = vrchol;
                                }
                        }

                        // ideme hladat vrchol s min hodnotou, ktory nie je vybaveny
                        for (int i = 0; i < ms.length; i++) {
                                if (!vybavene[i] && hodnoty[i] < minHodnota) {
                                        minHodnota = hodnoty[i];
                                        minIdx = i;
                                }
                        }

                        vybavene[minIdx] = true;
                        vrchol = minIdx;
                        pocetVybavenych++;
                }

                for (int i = 0; i < ms.length; i++) {
                        if (i == s)
                                continue;

                        mst.add(new Hrana(predchodcovia[i], i, ms[predchodcovia[i]][i]));
                }

                return mst;
        }

        public static List<Hrana> kruskal(double[][] ms) {
                List<Hrana> mst = new ArrayList<Hrana>(ms.length - 1);
                int[] mnoziny = new int[ms.length];
                for (int i = 0; i < ms.length; i++)
                        mnoziny[i] = i;

                Set<Hrana> hrany = new HashSet<Hrana>();
                for (int i = 0; i < ms.length; i++) {
                        for (int j = 0; j < ms.length; j++)
                                if (ms[i][j] != NIE_JE_HRANA) {
                                        hrany.add(new Hrana(i, j, ms[i][j]));
                                }
                }

                Hrana[] utriedeneHrany= hrany.toArray(new Hrana[0]);
                Arrays.sort(utriedeneHrany);

                for (Hrana h : utriedeneHrany) {
                        System.out.println(h);
                        if (mnoziny[h.getVrchol1()] == mnoziny[h.getVrchol2()])
                                continue;

                        mst.add(h);
                        int id = mnoziny[h.getVrchol2()];
                        for (int i = 0; i < mnoziny.length; i++)
                                if (mnoziny[i] == id)
                                        mnoziny[i] = mnoziny[h.getVrchol1()];
                }

                return mst;
        }

        public static void main(String[] args) {
//              double[][] ms = new double[][]
//                              {
//                                      {NIE_JE_HRANA, 5, 5},
//                                      {5, NIE_JE_HRANA, 10},
//                                      {5, 10, NIE_JE_HRANA}
//                              };

                double[][] ms = new double[][]
                                {
                                        {NIE_JE_HRANA, 1, 2, NIE_JE_HRANA},
                                        {1, NIE_JE_HRANA, NIE_JE_HRANA, 2},
                                        {2, NIE_JE_HRANA, NIE_JE_HRANA, 2},
                                        {NIE_JE_HRANA, 2, 2, NIE_JE_HRANA}
                                };

                //List<Hrana> mst = dijkstraPrim(ms);
                List<Hrana> mst = kruskal(ms);
                System.out.println(mst);
        }
}

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class src {

        public static boolean debug = true;

        class Interval {
                double zaciatok, koniec;

                public Interval(double start, double end) {
                        super();
                        this.zaciatok = start;
                        this.koniec = end;
                }

        }

        class PorovnavacZaciatkov implements Comparator<Interval> {

                @Override
                public int compare(Interval i1, Interval i2) {
                        if (i1.zaciatok == i2.zaciatok)
                                return (int) Math.signum(i2.koniec - i1.koniec);
                        return (int) Math.signum(i1.zaciatok - i2.zaciatok);
                }

        }

        public int intervaly(File in) {

                List<Interval> list = nacitaj(in);
                Collections.sort(list, new PorovnavacZaciatkov());
                int vysledok = 1;
                System.out.println("Interval :" + list.get(0).zaciatok
                                + "-" + list.get(0).koniec);
                double koniec = list.get(0).koniec;
                // predstav si to ako salamu
                // a chces si ju dat na chleba
                //
                // Martin (16.5.2012)
                double najKoniec = koniec;

                for (int i = 1; i < list.size(); i++) {
                        if (list.get(i).koniec <= koniec) {
                                continue;
                        }

                        if (list.get(i).zaciatok >= koniec) {
                                if (debug)
                                        System.out.println("Interval :" + list.get(i).zaciatok
                                                        + "-" + list.get(i).koniec);
                                vysledok++;
                                koniec = najKoniec;
                        }

                        if (list.get(i).koniec > najKoniec) {
                                najKoniec = list.get(i).koniec;
                        }

                }

                return vysledok;
        }

        private List<Interval> nacitaj(File in) {
                Scanner sc = null;
                List<Interval> list = null;
                try {
                        sc = new Scanner(in);
                        int dvojic = sc.nextInt();
                        list = new ArrayList<src.Interval>(dvojic);
                        for (int i = 0; i < dvojic; i++) {
                                list.add(new Interval(sc.nextDouble(), sc.nextDouble()));
                        }
                } catch (FileNotFoundException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                }
                return list;
        }

        public static void main(String[] args) {
                System.out.println(new src().intervaly(new File("intervaly1")));
        }
}

import java.io.*;
import java.util.*;

public class src2 {

        public static class Edge {
                String air1, air2;

                public Edge(String air1, String air2) {
                        this.air1 = air1;
                        this.air2 = air2;
                }
        }

        public static boolean[][] nacitaj(File in) {
                Scanner sc = null;
                List<Edge> list = new LinkedList<Edge>();
                Set<String> set = new HashSet<String>();
                boolean[][] ms = null;
                try {
                        sc = new Scanner(in);
                        while (sc.hasNext()) {
                                String string1 = sc.next();
                                String string2 = sc.next();
                                list.add(new Edge(string1, string2));
                                set.add(string1);
                                set.add(string2);
                        }
                        ms = new boolean[set.size()][set.size()];
                        for (boolean[] boolArray : ms) {
                                Arrays.fill(boolArray, false);
                        }
                        // Ideme naplnit maticu
                        List<String> pastArray = new ArrayList<String>(set);
                        for (Edge edge : list) {
                                int vrchol1 = pastArray.indexOf(edge.air1);
                                int vrchol2 = pastArray.indexOf(edge.air2);
                                ms[vrchol1][vrchol2] = true;
                                ms[vrchol2][vrchol1] = true;
                        }
                } catch (FileNotFoundException e) {
                        e.printStackTrace();
                } finally {
                        if (sc != null)
                                sc.close();
                }

                return ms;
        }

        public static int solve(File in) {
                boolean[][] ms = nacitaj(in);
                int[] array = Grafy.komponentyGrafu(ms);
                int solution = 0;
                for (int i = 0; i < array.length; i++) {
                        solution = Math.max(solution, array[i]);
                }
                return solution - 1;
        }

        public static void main(String[] args) {
                System.out.println(solve(new File("intervaly1")));
        }
}