바이러스

문제

바이러스

풀이

1번 컴퓨터에서 도달할 수 있는 컴퓨터는 모두 감염됩니다. 1번 컴퓨터를 시작으로 DFS 탐색하여 방문한 총 컴퓨터의 개수를 출력하면 됩니다. 단, 개수를 셀 때 1번 컴퓨터는 제외해야 합니다.

코드

Python

n = int(input())
 
adj = [[] for _ in range(n + 1)]
 
for _ in range(int(input())):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
 
visited = [False] * (n + 1)
 
 
def dfs(u: int) -> int:
    visited[u] = True
    ret = 1
 
    for v in adj[u]:
        if not visited[v]:
            ret += dfs(v)
    return ret
 
 
print(dfs(1) - 1)

C++

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<bool> visited;
 
int dfs(int u) {
    visited[u] = true;
    int ret = 1;
 
    for (int v : adj[u]) {
        if (not visited[v])
            ret += dfs(v);
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    adj = vector(n + 1, vector<int>());
    visited = vector(n + 1, false);
 
    int m;
    cin >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    cout << dfs(1) - 1;
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i <= n; i++)
            adj.add(new ArrayList<>());
        visited = new boolean[n + 1];
        
        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(tk.nextToken()),
                v = Integer.parseInt(tk.nextToken());
            
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
 
        bw.write(dfs(1) - 1 + "");
        bw.close();
    }
 
    static int dfs(int u) {
        visited[u] = true;
        int ret = 1;
 
        for (int v : adj.get(u)) {
            if (!visited[v])
                ret += dfs(v);
        }
 
        return ret;
    }
}