java-programs-/KruskalAlgorithm.java at master · Devils-judge/java-programs- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package Graph;

import java.util.*;

public class KruskalAlgorithm {
    static class Node implements Comparable<Node>
    {
        int src;
        int dest;
        int weight;
        Node(int src,int dest,int weight)
        {
            this.src=src;
            this.dest=dest;
            this.weight=weight;
        }
        public int compareTo(Node n)
        {
            return this.weight-n.weight;
        }
    }

    static class SortingWay implements Comparator<Node>
    {
        public int compare(Node p,Node n)
        {
            return p.weight-n.weight;
        }
    }

    public static int findParent(int n,int[] parent)
    {
        if(n==parent[n])
        {
            return n;
        }
        return parent[n]=findParent(parent[n],parent);
    }
    public static void union(int n,int m,int[] parent,int[] rank)
    {
        n=findParent(n,parent);
        m=findParent(m,parent);
        if(rank[n]<rank[m])
        {
            parent[n]=m;
        }else if(rank[n]>rank[m])
        {
            parent[m]=n;
        }else
        {
            parent[m]=n;
            rank[n]++;
        }
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        if(n==0)
        {
            System.out.println("0");
            return ;
        }
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i]= scan.nextInt();
        }
        int count=1;
        ArrayList<Integer> ans=new ArrayList<>();
        ans.add(arr[0]);
       for(int i=1;i<n;i++)
       {
           if(arr[i-1]!=arr[i])
           {
               count++;
               ans.add(arr[i]);
           }
       }
       System.out.println(count);
       for(int i:ans)
       {
           System.out.print(i+" ");
       }
//        int V=scan.nextInt();
//        int E=scan.nextInt();
//        ArrayList<Node> graph=new ArrayList<>();
//        for(int i=0;i<E;i++)
//        {
//            int src=scan.nextInt();
//            int dest= scan.nextInt();
//            int weight=scan.nextInt();
//            graph.add(new Node(src,dest,weight));
//            graph.add(new Node(dest,src,weight));
//        }
//        int[] parent=new int[V];
//        int[] rank=new int[V];
//        for(int i=0;i<V;i++)
//        {
//            parent[i]=i;
//        }
//        ArrayList<Node> ans=new ArrayList<>();
//        Collections.sort(graph,new SortingWay());
//        for(Node n:graph)
//        {
//            if(findParent(n.src,parent)!=findParent(n.dest,parent))
//            {
//                union(n.src,n.dest,parent,rank);
//                ans.add(n);
//            }
//        }
//
//        for(Node n:ans)
//        {
//            System.out.println(n.src+" "+n.dest+" "+n.weight);
//        }
    }
}