C11

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

import sk.upjs.paz.graph.Edge;
import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;


public class PrimovAlgoritmus {

        public static Set<Edge> minimalnaKostra(Graph g) {
                Set<Vertex> nevybavene = new HashSet<Vertex>();
                nevybavene.addAll(g.getVertices());

                Vertex r = null;
                for (Vertex v : nevybavene) {
                        v.setValue("hodnota", Double.POSITIVE_INFINITY);
                        r = v;
                }
                r.setValue("hodnota", 0);

                while (!nevybavene.isEmpty()) {
                        for (Vertex v : r.getNeighbours()) {
                                double h = g.getEdge(r, v).getWeight();
                                if (nevybavene.contains(v) && v.getDoubleValue("hodnota") > h) {
                                        v.setValue("hodnota", h);
                                        v.setValue("predchodca", r);
                                }
                        }

                        nevybavene.remove(r);

                        double minHodnota = Double.POSITIVE_INFINITY;
                        for (Vertex v : nevybavene) {
                                if (minHodnota > v.getDoubleValue("hodnota")) {
                                        r = v;
                                        minHodnota = v.getDoubleValue("hodnota");
                                }
                        }
                        if (minHodnota == Double.POSITIVE_INFINITY && !nevybavene.isEmpty())
                                return new HashSet<Edge>();
                }

                //pozbierame hrany
                Set<Edge> hrany = new HashSet<Edge>();
                for (Vertex v : g.getVertices()) {
                        Vertex pred = (Vertex) v.getValue("predchodca");
                        if (pred != null) {
                                hrany.add(g.getEdge(v, pred));
                        }
                }
                return hrany;
        }

        public static Graph nacitajGraf() {
                Scanner s = new Scanner(System.in);
                String[] pom = s.nextLine().split(" ");
                int pocetVrcholov = Integer.parseInt(pom[0]);
                int pocetHran = Integer.parseInt(pom[0]);

                //pridanieVrcholov
                Graph g = new Graph();
                for (int i = 1; i <= pocetVrcholov; i++) {
                        g.addVertex(i + "");
                }

                //nacitanie hran
                for (int i = 0; i < pocetHran; i++) {
                        String[] hrana = s.nextLine().split(" ");
                        g.addEdge(g.getVertex(hrana[0]), g.getVertex(hrana[1]));
                        g.getEdge(g.getVertex(hrana[0]), g.getVertex(hrana[1]))
                                .setWeight(Double.parseDouble(hrana[2]));
                }

                return g;
        }

        public static void main(String[] args) {
                Scanner s = new Scanner(System.in);
                int pocetVstupov = s.nextInt();
                for (int i = 0; i < pocetVstupov; i++) {
                        Graph g = nacitajGraf();
                        Set<Edge> kostra = minimalnaKostra(g);
                        System.out.println(kostra);
                }

//              Graph g = new Graph();
//              g.loadFromFile("graf.txt");
//              g.setDirected(false);
//             
//              Set<Edge> kostra = minimalnaKostra(g);
//              System.out.println(kostra);
        }

}
 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

import sk.upjs.paz.graph.Edge;
import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;

public class KruskalovAlgoritmus {

        public static Set<Edge> vypocitaj(Graph g) {

                for (Vertex v : g.getVertices()) {
                        v.setValue("komponent", v.getLabel());

                }
                ArrayList<Edge> hrany = new ArrayList<Edge>();
                hrany.addAll(g.getEdges());
                Collections.sort(hrany, new Comparator<Edge>() {

                        @Override
                        public int compare(Edge o1, Edge o2) {
                                if (o1.getWeight() < o2.getWeight())

                                        return -1;
                                if (o1.getWeight() == o2.getWeight())
                                        return 0;

                                return 1;
                        }

                });
                System.out.println(hrany);
                Set<Edge> kostra = new HashSet<Edge>();
                for (Edge e : hrany) {
                        if (e.getSource().getValue("komponent").equals(e.getTarget().getValue("komponent"))) {
                                continue;
                        }
                        kostra.add(e);
                        for (Vertex v : g.getVertices()) {
                                if(v.getValue("komponent").equals(e.getTarget().getValue("komponent"))){
                                        v.setValue("komponent", e.getSource().getValue("komponent"));
                                }
                        }
                }
                return kostra;
        }

        public static void main(String[] args) {
                Graph g = new Graph();
                g.loadFromFile("graf.txt");
                System.out.println(vypocitaj(g));

        }

}
 

import java.util.ArrayList;
import java.util.Scanner;

public class FestivaloveLeto {

        public static ArrayList<Integer> zaciatky = new ArrayList<Integer>();
        public static ArrayList<Integer> konce = new ArrayList<Integer>();

        public static void nacitaj() {
                Scanner sc = new Scanner(System.in);
                int pocet = sc.nextInt();

                for (int i = 0; i < pocet; i++) {
                        zaciatky.add(sc.nextInt());
                        konce.add(sc.nextInt());
                }

        }

        public static void utried() {
                for (int i = 0; i < zaciatky.size(); i++) {
                        for (int j = 0; j < zaciatky.size() - i-1; j++) {
                                if (konce.get(j) > konce.get(j + 1)) {
                                        konce.add(j, konce.get(j + 1));
                                        konce.remove(j + 2);
                                        zaciatky.add(j, zaciatky.get(j + 1));
                                        zaciatky.remove(j + 2);
                                }
                        }
                }
        }

        public static ArrayList<Integer> vypocitaj() {
                ArrayList<Integer> vysledok = new ArrayList<Integer>();
                vysledok.add(0);
                for (int i = 1; i < konce.size(); i++) {
                        if (zaciatky.get(i) > konce
                                        .get(vysledok.get(vysledok.size() - 1))) {
                                vysledok.add(i);

                        }

                }
                return vysledok;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                nacitaj();
                utried();
                System.out.println(zaciatky);
                System.out.println(konce);
                System.out.println(vypocitaj());
        }

}