백준 2606 - 바이러스, 너비우선, 깊이우선, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, bfs,dfs

 

// Process
// 1. Input computerNumber, pairNumber, pairArray
// 2. Make graph with inputs
// 3. (DFS) start with 1st computer, put 1st in the stack
// 4. Iterate while stack is empty
//  4.1. pop and count
//  4.2. check all adjacent of popped one
//   4.2.1. If it's not visited yet -> put that in the stack
// 5. Return count

 

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

class Virus {
    public static void main(String args[]) throws IOException {

        // 1.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int computers = Integer.parseInt(br.readLine());
        int pairs = Integer.parseInt(br.readLine());
        
        VertexCpu[] vertexes = new VertexCpu[computers];
        for (int i = 0; i < vertexes.length; ++i) {
            vertexes[i] = new VertexCpu(i);
        }

        // 2.
        for (int i = 0; i < pairs; ++i) {
            String[] temp = br.readLine().split(" ");
            vertexes[(Integer.parseInt(temp[0]) - 1)].addAdjacent(vertexes[Integer.parseInt(temp[1]) - 1]);
        }
        
        int count = 0;

        // 3. 
        Stack<VertexCpu> stack = new Stack<>();
        stack.add(vertexes[0]);

        while (stack.size() > 0) {
            VertexCpu temp = stack.pop();

            if (!temp.isVisited) {
                temp.isVisited = true;

                ++count;

                for (int i = 0; i < temp.adjacents.size(); ++i) {
                    if (!temp.adjacents.get(i).isVisited) {
                        stack.push(temp.adjacents.get(i));
                        // temp.adjacents.get(i).isVisited = true;
                    }
                }
            }
        }

        System.out.println(--count);

        // for (int i = 0; i < vertexes.length; ++i) {
        //     for (int j = 0; j < vertexes[i].adjacents.size(); ++j) {
        //         System.out.print(vertexes[i].adjacents.get(j).number + " ");
        //     }
        //     System.out.println("");
        // }
    }


}

class VertexCpu {
    int number;
    boolean isVisited;
    List<VertexCpu> adjacents;

    public VertexCpu(int number) {
        this.number = number;
        this.isVisited = false;
        this.adjacents = new LinkedList<>();
    }

    public void addAdjacent(VertexCpu dstVertex) {
        if (!adjacents.contains(dstVertex)) {
            adjacents.add(dstVertex);
            dstVertex.adjacents.add(this);
        } 
    }
}

 

 

2021.04.01 - [Algorithm/Baekjoon_acmicpc] - 백준 1715 - 카드 정렬하기, 문제풀이, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, acmicpc

백준 1715 - 카드 정렬하기, 문제풀이, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스

2019.08.11 - [Algorithm/Leet Code] - LeetCode #896 MonotonicArray. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트

LeetCode #896 MonotonicArray. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문