import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class virus_2606 {
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int v = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken());
graph = new ArrayList[v + 1];
for (int i = 0; i < v+1; i++){
graph[i] = new ArrayList<>();
}
visited = new boolean[v + 1];
for (int i = 0; i < w; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a].add(b);
graph[b].add(a);
}
int start = 1;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : graph[node]) {
if (!visited[next]) {
count++;
queue.offer(next);
visited[next] = true;
}
}
}
System.out.println(count);
}
}
주어진 코드는 바이러스의 전파를 나타내는 그래프에서 1번 노드부터 시작하여 BFS(Breadth-First Search)를 수행하여 전체 감염된 노드의 수를 계산하는 로직입니다. 아래는 해당 코드의 로직을 설명한 것입니다.
v
)와 간선 수(w
)를 읽어옵니다.graph
배열을 초기화합니다. graph
는 각 노드의 인접 리스트를 저장하는 배열로, 각 노드에 연결된 인접한 노드들을 저장합니다.visited
배열을 초기화합니다. visited
는 각 노드의 방문 여부를 저장하는 배열로, 방문한 노드는 true
로 표시됩니다.graph
배열에 저장합니다. 입력으로 주어지는 두 노드 사이에 양방향 간선이 존재하므로, 양쪽 방향으로 간선을 추가합니다.1
을 큐(queue
)에 삽입하고, 해당 노드를 방문 처리합니다.count
를 초기화합니다.node
)를 꺼냅니다.node
)와 인접한 노드(next
)를 순회합니다.next
)가 방문되지 않은 경우, 감염된 노드의 수(count
)를 증가시키고, 인접한 노드를 큐에 삽입하고 방문 처리합니다.count
값을 출력합니다. 이 값은 시작 노드인 1번 노드를 통해 감염된 전체 노드의 수를 나타냅니다.const readline = require("readline");
let v, w;
const graph = [];
const input = [];
readline
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
v = parseInt(input[0]);
w = parseInt(input[1]);
const visited = new Array(v + 1).fill(false);
for (let j = 0; j < v + 1; j++) {
graph.push(new Array());
}
for (let i = 2; i < input.length; i++) {
const [a, b] = input[i].split(" ").map(Number);
graph[a].push(b);
graph[b].push(a);
}
const queue = [];
queue.push(1);
visited[1] = true;
let count = 0;
while (queue.length > 0) {
const node = queue.shift();
for (const next of graph[node]) {
if (!visited[next]) {
count++;
queue.push(next);
visited[next] = true;
}
}
}
console.log(count);
process.exit();
});
from collections import deque
v = int(input())
w = int(input())
graph = [[] for _ in range(v + 1)]
visited = [False] * (v + 1)
for _ in range(w):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
start = 1
queue = deque()
queue.append(start)
visited[start] = True
count = 0
while queue:
node = queue.popleft()
for next_node in graph[node]:
if not visited[next_node]:
count += 1
queue.append(next_node)
visited[next_node] = True
print(count)