삼성 SDS 대학생 알고리즘 특강 6일차 - 그래프

그래프 종류

• 무향 그래프
• 유향 그래프
• 가중치 그래프
• 정규 그래프
• 완전 그래프
• 연결 그래프
• 부분 그래프
• 트리 그래프

 

1717: 집합의 표현

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

public class Main {
    static int[] parent, depth;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[N + 1];
        depth = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            depth[i] = 1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (command == 0) {
                union(a, b);
            } else if (command == 1) {
                sb.append((find(a) == find(b) ? "YES" : "NO") + "\n");
            } else {
                continue;
            }
        }
        System.out.println(sb);
        br.close();
    }

    public static int find(int x) {
        return parent[x] = (x == parent[x]) ? x :find(parent[x]);
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (depth[x] < depth[y]) {
                int tmp = x;
                x = y;
                y = tmp;
            }
            parent[y] = x;
            if (depth[x] == depth[y]) depth[x]++;
        }
    }
}

 

2252: 줄 세우기

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] in = new int[N+1];
        ArrayList<Integer>[] adj = new ArrayList[N+1];
        for(int i = 0; i < N+1; i++) {
            adj[i] = new ArrayList();
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            adj[from].add(to);
            in[to]++;
        }
        Queue<Integer> q = new LinkedList();
        for(int i = 1; i < N+1; i++) {
            if(in[i] == 0) {
                q.add(i);
            }
        }
        while(!q.isEmpty()) {
            int now = q.poll();
            sb.append(now).append(" ");
            for(int next: adj[now]) {
                in[next]--;
                if(in[next] == 0) {
                    q.add(next);
                }
            }
        }
        System.out.println(sb);     
    }
}

 

 

1922: 네트워크 연결

import java.util.*;
import java.io.*;
public class Main {
    static int N;
    static int M;
    static int[] parent;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        parent = new int[N+1];
        for(int i = 1; i <= N; i++){
            parent[i] = i;
        }
        int a, b, c;
        for(int i = 0 ; i < M; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            pq.add(new int[]{a,b,c});
        }
        int cnt = 0, total = 0;
        while(cnt < N-1 && !pq.isEmpty()){
            int[] tmp = pq.poll();
            if(find(tmp[0]) != find(tmp[1])){
                cnt++;
                union(tmp[0], tmp[1]);
                total += tmp[2];
            }
        }
        System.out.println(total);
    }
    static int find(int x){
        return parent[x] = (parent[x] == x) ? x : find(parent[x]);
    }
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        parent[a] = b;
    }
}