School algo09 탐욕적(Greedy) 알고리즘2.

# 크루스칼 #union-find 서로소인 집합을 찾는 집합 자료구조 알고리즘

A. 가중치 무방향 그래프에서 최소신장트리 구하기

 

Sol1) 우선순위 큐를 이용한 Prim 알고리즘(인접리스트 이용)

//원본!!!!!! 좀 더 실용적인 코드는 아래에!
//인접 행렬=방향, 밀집, (무방향도 인접행렬로 표현하는 것이 빈번)
//인접 리스트=무방향, 희소

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Practice {
    public static final int INF = 987654321;

    public static class Edge {
        private int to;
        private int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Node {
        private int node;
        private int weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        public int weight() {
            return weight;
        }
    }
//Node에는 Node이름과 weight값(해당 정점까지의 거리를 의미함).  Edge에는 목적지 정점(to)과 가중치(weight)
    public static int solve(List<List<Edge>> G) {
        PriorityQueue<Node> que = new PriorityQueue<>(Comparator.comparing(Node::weight));
        boolean[] visited = new boolean[G.size()];
        int total = 0;
        int[] distance = new int[G.size()];
        Arrays.fill(distance, INF);
        distance[0] = 0;
//아래는 좀더 효율적이고 파이썬코드와 일치시키기고자 주석처리 한다.
//        visited[0] = true;
//        for (var edge : G.get(0)) {
//            distance[edge.to] = edge.weight;
//            que.add(new Node(edge.to, edge.weight));
//        }
        que.add(new Node(0, 0));
        while (!que.isEmpty()) {
            Node curr = que.remove();
            if (visited[curr.node]) continue;
            visited[curr.node] = true;
            total += curr.weight;
            for (var edge : G.get(curr.node)) {
                if (!visited[edge.to] && edge.weight < distance[edge.to]) {
                    distance[edge.to] = edge.weight;
                    que.add(new Node(edge.to, edge.weight));
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {
        try (
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            int T = Integer.parseInt(br.readLine());
            for (int t = 0; t < T; ++t) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int N = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int[] data = Arrays.stream(br.readLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
                List<List<Edge>> G = new ArrayList<>(N);
                for (int i = 0; i < N; ++i) G.add(new ArrayList<Edge>());
                //List<Edge>[] G2=new ArrayList[N+1];위와 같은 표현
                //for (int i = 0; i < G2.length; i++) G2[i] = new ArrayList<>();
                int j = 0;
                for (int i = 0; i < E; ++i) {
                    int u = data[j++];
                    int v = data[j++];
                    int w = data[j++];
                    G.get(u).add(new Edge(v, w));
                    G.get(v).add(new Edge(u, w));
                }
                System.out.println(solve(G));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}











//Edge class를 없앤 좀 더 실용적인 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class Practice3 {
    public static final int INF=98765541;
    public static class Node{
        private int node;
        private int weight;

        public Node(int node, int weight){
            this.node=node;
            this.weight=weight;
        }
        public int weight(){
            return this.weight;
        }
    }
    public static int solve(List<List<Node>> graph){
        PriorityQueue<Node>que=new PriorityQueue<>(Comparator.comparingInt(Node::weight));
        int size=graph.size();
        boolean[]visited=new boolean[size];
        int total=0;
        int[]distance=new int[size];
        Arrays.fill(distance, INF);
        distance[0]=0;

        que.add(new Node(0,0));
        while(!que.isEmpty()){
            Node cur=que.poll();
            if(visited[cur.node])continue;
            visited[cur.node]=true;
            total+=cur.weight;
            for(var node:graph.get(cur.node)){
                if(!visited[node.node] && node.weight<distance[node.node]){
                    distance[node.node]=node.weight;
                    que.add(new Node(node.node, node.weight));
                }
            }
        }
        return total;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for (int t=0;t<T;t++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int N=Integer.parseInt(st.nextToken());
            int E=Integer.parseInt(st.nextToken());
            int[]data= Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            List<List<Node>>graph=new ArrayList<>(N);
            for(int i=0;i<N;i++)
                graph.add(new ArrayList<>());
            int j=0;
            for(int i=0;i<E;i++){
                int u=data[j++];
                int v=data[j++];
                int w=data[j++];
                graph.get(u).add(new Node(v,w));
                graph.get(v).add(new Node(u, w));
            }
            System.out.println(solve(graph));
        }
    }
}

Sol1) 우선순위 큐를 이용한 Prim 알고리즘(인접행렬 이용)

//프림은 정점을 탐욕적으로 n개 선택해 나가는 알고리즘이다. 구체적인 방법은 임의의 정점의 dist를 0으로 만들고 정점을 선택함에 따라
// 매번 dist배열을 매번 갱신해 가는 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Testing3{
    static class Vertex{
        int vertex;
        int weight;//이전정점에서 현재 정점까지의 거리
        public Vertex(int vertex, int weight){
            this.vertex=vertex;
            this.weight=weight;
        }
        public int getWeight(){
            return weight;
        }
    }
    public static final int INF=987654321;
    public static int solution(int[][]graph){
        PriorityQueue<Vertex>pq=new PriorityQueue<>(Comparator.comparingInt(Vertex::getWeight));
        int vSize=graph.length;
        int[]distance=new int[vSize];
        Arrays.fill(distance, INF);
        distance[0]=0;
        pq.add(new Vertex(0,0));
        int numOfVertex=0;
        boolean[]visited=new boolean[vSize];
        int sum=0;
        while(numOfVertex<vSize){
            Vertex v=pq.poll();
            if(!visited[v.vertex]){
                visited[v.vertex]=true;
                sum+=distance[v.vertex];
                ++numOfVertex;
                for(int u=0;u<vSize;u++){
                    if(graph[v.vertex][u]!=INF && graph[v.vertex][u]<distance[u]) {
                        distance[u] = graph[v.vertex][u];
                        pq.add(new Vertex(u, distance[u]));
                    }
                }
            }
        }
        return sum;
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int t=0;t<T;t++){
            st=new StringTokenizer(br.readLine());
            int vertex=Integer.parseInt(st.nextToken());
            int edge=Integer.parseInt(st.nextToken());
            int[][]graph=new int[vertex][vertex];
            for(int i=0;i<vertex;i++)
                Arrays.fill(graph[i], INF);
            int[]data=Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int j=0;
            for(int i=0;i<edge;i++){
                int v1=data[j++];
                int v2=data[j++];
                int weight=data[j++];
                graph[v1][v2]=weight;
                graph[v2][v1]=weight;
            }
            System.out.println(solution(graph));


        }
    }
}

 

 

Sol2) Union-find 자료구조를 이용한 Kruskal 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
   
public class Main {
    private static final int INF = 987564321;
    public static class Edge {
        private int from;
        private int to;
        private int weight;
        public Edge(int from, int to, int weight) { 
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public int from(){
            return from;
        }
        public int to() {
            return to;
        }
        public int weight() {
            return weight;
        }
    }
  
    public static class UnionFind {
        private int[] parent;
        private int[] size;
        public UnionFind(int numNodes) {
            parent = new int[numNodes];
            size = new int[numNodes];
            for(int i = 0; i < numNodes; ++i){
                parent[i] = i;
                size[i] = 1;
            }
        }
   
        public int find(int x) {
            if(x==parent[x]) return x;
            return parent[x] = find(parent[x]);
        }
   
        public boolean union(int x, int y){
            x = find(x);
            y = find(y);
            if(x != y) {
                if(size[x]>=size[y]) {
                    parent[y] = x; 
                    size[x] += size[y]; 
                    size[y] = 0; 
                }
                else {
                    parent[x] = y;
                    size[y] += size[x];
                    size[x] = 0;
                }
                return true;
            }
            return false;
        }
    }
       
    public static int solve(int N, List<Edge> edges) {
        UnionFind U = new UnionFind(N);
        edges.sort(Comparator.comparingInt(Edge::weight));
        int total = 0;
        for(var edge: edges) {
            if(U.union(edge.from(), edge.to()))
                total += edge.weight();
        }
        return total;
    }
       
    public static void main(String[] args) {
        try(
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ){
            int T = Integer.parseInt(br.readLine());
            for(int t=0; t<T; ++t){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int N = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int[] data = Arrays.stream(br.readLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
                List<Edge> edges = new ArrayList<>();
                int j=0;
                for(int i=0; i<E; ++i) {
                    int u = data[j++];
                    int v = data[j++];
                    int w = data[j++];
                    edges.add(new Edge(u,v,w));
                }
                System.out.println(solve(N, edges));
            }
        }
        catch(Exception e){
            e.printStackTrace();
        }
    }
}

 

Union-find집합 자료구조, 우선순위 큐, record를 사용한 크루스칼 알고리즘. 아래 코드에서 보는 것과 같이 record불변 클래스를 만드렁 줌에 따라 생성자와 정렬하기 위해 사용되었던 getWeight()메서드를 따로 생성해 주지 않아서 훨씬 간결해 졌다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main{
 
    //record로도 만들어 보기
//    static class Edge{
//        int start;
//        int end;
//        int weight;
//        public Edge(int start, int end, int weight){
//            this.start=start;
//            this.end=end;
//            this.weight=weight;
//        }
//        int getWeight(){
//            return weight;
//        }
//    }
    static record Edge(int start, int end, int weight){
         
    }
    //union find= 집합 자료구조. 서로소인 집합을 표현하는 집합자료구조
    static class Union_find {
        int[] parent;
        int[] size;
        public Union_find(int vSize) {
            parent = new int[vSize];
            size = new int[vSize];
            for (int i = 0; i < parent.length; i++) {
                parent[i]=i;
                size[i]=1;
            }
        }
        int find(int vertex){
            if(parent[vertex]==vertex)
                return vertex;
            parent[vertex]=find(parent[vertex]);
            return parent[vertex];
        }
        //오직 부모가 달랐을 때만 union하기
        void union(int v1, int v2) {
            if (size[v1] <= size[v2]) {
                size[v2] += size[v1];
                size[v1] = 0;
                parent[v1] = v2;
            } else {
                size[v1] += size[v2];
                size[v2] = 0;
                parent[v2] = v1;
            }
        }
    }
    public static int solution(int vSize, PriorityQueue<Edge>pq){
        Union_find uf=new Union_find(vSize);
        int answer=0;
        int n=0;
        while(n<vSize-1){
            Edge edge=pq.poll();
            int start=edge.start;
            int end=edge.end;
            int u1=uf.find(start);
            int u2=uf.find(end);
            if(u1!=u2) {
                ++n;
                uf.union(u1, u2);
                answer+=edge.weight;
            }
        }
        return answer;
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int t=0;t<T;t++){
            PriorityQueue<Edge> pq=new PriorityQueue<>(Comparator.comparingInt(Edge::weight));
            st=new StringTokenizer(br.readLine());
            int v=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            int[]data=Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int i=0;
            while(i<data.length) {
                int start = data[i++];
                int end = data[i++];
                int weight = data[i++];
                Edge edge = new Edge(start, end, weight);
                pq.add(edge);
            }
            System.out.println(solution(v, pq));
       }
    }
}

 

아래는 간선을 정렬후 사이클을 형성하지 않는 선에서  N-1개의 간선을 뽑늘 좀더 크루스칼 알고리즘의 본질에 다가선 풀이. List 컬랙션 자료구조를 사용하여 역순정렬한후 pop을 할수 없어 그냥 정렬후 Iterator를 사용해 주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static class Edge {
        private int from;
        private int to;
        private int weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public int from() {
            return from;
        }
        public int to() {
            return to;
        }
        public int weight() {
            return weight;
        }
    }

    public static class UnionFind {
        private int[] parent;
        private int[] size;
        public UnionFind(int nodes) {
            parent = new int[nodes];
            size = new int[nodes];

            for (int i = 0; i < nodes; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int find(int id){
            if(parent[id]==id)
                return id;
            parent[id]=find(parent[id]);
            return parent[id];
            //한 큐에 return parent[id]=find(parent[id]); 도 가능함
        }

        public boolean union(int id1, int id2){
            int u=find(id1);
            int v=find(id2);
            if(u!=v){
                if(size[u]>=size[v]){
                    parent[v]=u;
                    size[u]+=size[v];
                    size[v]=0;
                }
                else{
                    parent[u]=v;
                    size[v]+=size[u];
                    size[u]=0;
                }
                return true;
            }
            else
                return false;
        }


    }

    public static int solution(int N, List<Edge>edges){
        UnionFind uni=new UnionFind(N);
        edges.sort(Comparator.comparingInt(Edge::weight));
        Iterator<Edge>it=edges.iterator();
        int answer=0;
        int edge_accepted=0;
        while(edge_accepted<N-1){
            Edge edge=it.next();
            if(uni.union(edge.from(), edge.to())) {
                answer += edge.weight();
                edge_accepted += 1;
            }
        }
        return answer;
//        for(int i=0;i<N-1;i++){
//            edges.
//            int v1=edge.to();
//            int v2=edge.from();
//            int w=edge.weight();
//            if(uni.union(v1, v2))
//                answer+=w;
//        }
//        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for(int t=0;t<T;t++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int N=Integer.parseInt(st.nextToken());
            int E=Integer.parseInt(st.nextToken());
            int[] data=Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            List<Edge>edges=new ArrayList<>();
            int j=0;
            for(int i=0;i<E;i++)
                edges.add(new Edge(data[j++], data[j++], data[j++]));
            System.out.println(solution(N, edges));

        }
    }
}

 

 

B. (Leetcode, 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree에서 변형한) 핵심 간선 찾기.

기본아이디어는 아래 그림과 같다(출처: https://www.youtube.com/watch?v=R0IPqIFsuCM&t=623s)

 

왜기존의 Kruskal알고리즘에서 사용하였던
while(edgeAccepted<vSize-1):
           edges.pop(-1)
처럼 while문과 pop을 사용하지 않나?

Union_find 집합 자료구조를 한번만 사용할 것이 아니므로. 한 번만 사용할것이 아니므로 pop을 해서 edges에 있는 요소를 없애면 안된다. 
위와 같은 이유로 pop을 사용할수 없게 되고 pop을 사용할 수 없으니 while문이 아닌 for 문을 사용하여 해당 인덱스의 간선에 접근하게 된다. 따라서 while문이 아닌 for문을 사용하게 되는 것이다. 

 

1)Through Kruskal

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
 
public class Main {
    public static class Edge {
        public int from;
        public int to;
        public int weight;
        public int index;
        public Edge(int from, int to, int weight, int index) {  
            this.from = from;
            this.to = to;
            this.weight = weight;
            this.index = index;
        }
        public int weight() {
            return weight;
        }
    }

    public static class UnionFind {
        private int[] parent;
        private int[] size;
        public UnionFind(int numNodes) {
            parent = new int[numNodes];
            size = new int[numNodes];
            for(int i = 0; i < numNodes; ++i){
                parent[i] = i;
                size[i] = 1;
            }
        }
    
        public int find(int x) {
            if(x == parent[x]) return x;
            return parent[x] = find(parent[x]);
        }
    
        public boolean union(int x, int y){
            x = find(x);
            y = find(y);
            if(x != y) {
                if(size[x] >= size[y]) {
                    parent[y] = x; 
                    size[x] += size[y]; 
                    size[y] = 0; 
                }
                else {
                    parent[x] = y;
                    size[y] += size[x];
                    size[x] = 0;
                }
                return true;
            }
            return false;
        }
    }
 
    public static int kruskal_omit_e(int n, Edge[] E, int omitted){
        UnionFind U = new UnionFind(n);
        int cost = 0;
        for(int i = 0; i < E.length; ++i) {
            if(i != omitted && U.union(E[i].from, E[i].to))
                cost += E[i].weight;
        }
        return cost;
    }
 
    public static int kruskal(int n, Edge[] E){
        UnionFind U = new UnionFind(n);
        int cost = 0;
        for(var e: E) 
            if(U.union(e.from, e.to)) cost += e.weight;
        return cost;
    }
 
    public static List<Integer> findCriticalEdges(int N, Edge[] E) {
        List<Integer> criticalEdges = new ArrayList<>();
         
        Arrays.sort(E, Comparator.comparingInt(Edge::weight));
        int minCost = kruskal(N, E);
         
        for(int i = 0; i < E.length; ++i)
            if(kruskal_omit_e(N, E, i) != minCost) criticalEdges.add(E[i].index);
        Collections.sort(criticalEdges);
        return criticalEdges;
    }   
     
    public static void main(String[] args) {
        try(
            BufferedReader in 
                = new BufferedReader(new InputStreamReader(System.in))
        ){
            int T = Integer.parseInt(in.readLine());
            for(int t = 0; t < T; ++t) {
                int[] graphInfo = Arrays.stream(in.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
                int[] edgeInfo = Arrays.stream(in.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
                Edge[] edges = new Edge[graphInfo[1]];
                for(int i = 0, j = 0; i<graphInfo[1]; ++i, j += 3)
                    edges[i] = new Edge(edgeInfo[j], edgeInfo[j + 1], edgeInfo[j + 2], i);
                List<Integer> criticalEdges = findCriticalEdges(graphInfo[0], edges);
                if(criticalEdges.size() == 0) System.out.println(-1);
                else System.out.println(criticalEdges.stream().map(idx -> idx.toString())
                    .collect(Collectors.joining(" ")));
            }
        }
        catch(Exception e) {
            e.printStackTrace();
        }
    }
}

 

2)Through Prim

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
  
public class Main {
    public static final int INF = 987654321;
    public static class Edge {
        private int from;
        private int to;
        private int weight;
        public Edge(int from, int to, int weight) { 
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
     
    public static class Node {
        private int node;
        private int weight;
        public Node(int node, int weight) {    
            this.node = node;
            this.weight = weight;
        }
        public int getWeight() {
            return weight;
        }
        @Override
        public boolean equals(Object other){
            return ((Node)other).node == node;  
        }
    }
 
    public static int prim(List<List<Node>> G){
        PriorityQueue<Node> H = new PriorityQueue<>(Comparator.comparing(Node::getWeight));
        boolean[] visited = new boolean[G.size()];
        int total = 0;
        int[] keys = new int[G.size()];
        Arrays.fill(keys, INF);
        keys[0] = 0;
        visited[0] = true;
        for(var edge: G.get(0)){
            keys[edge.to] = edge.weight;
            H.add(new Node(edge.to, edge.weight));
        }
        while(!H.isEmpty()){
            Node curr = H.remove();
            if(visited[curr.node]) continue;
            visited[curr.node] = true;
            total += curr.weight;
            for(var edge: G.get(curr.node)) {
                if(!visited[edge.node] && edge.weight < keys[edge.node]) {
                    keys[edge.node] = edge.weight;
                    H.add(new Node(edge.node, edge.weight));
                }
            }
        }
        return total;
    }

    public static List<Integer> solve(List<List<Node>> G, List<Edge> edgeList){
        int minCost = prim(G);
        List<Integer> ret = new ArrayList<>();
        int i = 0;
        for(var e: edgeList){
            G.get(e.to).remove(new Node(e.from, e.weight));
            G.get(e.from).remove(new Node(e.to, e.weight));
            if(minCost != prim(G)) ret.add(i);
            G.get(e.to).add(new Node(e.from, e.weight));
            G.get(e.from).add(new Node(e.to, e.weight));
            ++i;
        }
        return ret;
    }
      
    public static void main(String[] args) {
        try(
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ){
            int T = Integer.parseInt(br.readLine());
            for(int t = 0; t < T; ++t){
                StringTokenizer st = new StringTokenizer(br.readLine());
                int N = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                List<List<Node>> G = new ArrayList<>(N);
                List<Edge> edgeList = new ArrayList<>(E);
                for(int i = 0; i < N; ++i) G.add(new LinkedList<Node>());
                int j = 0;
                for(int i = 0; i < E; ++i) {
                    int u = data[j++];
                    int v = data[j++];
                    int w = data[j++];
                    G.get(u).add(new Node(v, w));
                    G.get(v).add(new Node(u, w));
                    edgeList.add(new Edge(u, v, w));
                }
                List<Integer> criticalEdges = solve(G, edgeList);
                if(criticalEdges.size() == 0) System.out.println(-1);
                else System.out.println(criticalEdges.stream().map(idx -> idx.toString())
                    .collect(Collectors.joining(" ")));
            }
        }
        catch(Exception e){
            e.printStackTrace();
        }
    }
}