그래프와 깊이 우선 탐색

n, m = map(int, input().split())adj = [[] for _ in range(n + 1)]  # adj[v] = v번의 친구들for _ in range(m):    a, b = map(int, input().split())    adj[a].append(b)  # 서로 친구라 양쪽에 넣어요    adj[b].append(a) seen = [False] * (n + 1)order = [] def dfs(v):  # 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요    seen[v] = True    order.append(v)    for w in adj[v]:        if not seen[w]:            dfs(w) dfs(1)print(*order) # 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = [False] * (n + 1)groups = 0for s in range(1, n + 1):    if seen[s]:        continue    groups += 1    seen[s] = True    stack = [s]    while stack:        v = stack.pop()        for w in adj[v]:            if not seen[w]:                seen[w] = True                stack.append(w)print(groups)

const [[n, m], ...pairs] = require("fs").readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj = Array.from({ length: n + 1 }, () => []); // adj[v] = v번의 친구들for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b); // 서로 친구라 양쪽에 넣어요  adj[b].push(a);} let seen = new Array(n + 1).fill(false);const order = []; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요function dfs(v) {  seen[v] = true;  order.push(v);  for (const w of adj[v]) {    if (!seen[w]) dfs(w);  }} dfs(1);console.log(order.join(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = new Array(n + 1).fill(false);let groups = 0;for (let s = 1; s <= n; s++) {  if (seen[s]) continue;  groups++;  seen[s] = true;  const stack = [s];  while (stack.length > 0) {    const v = stack.pop();    for (const w of adj[v]) {      if (!seen[w]) {        seen[w] = true;        stack.push(w);      }    }  }}console.log(groups);

import { readFileSync } from "node:fs";const [[n, m], ...pairs]: number[][] = readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj: number[][] = Array.from({ length: n + 1 }, () => []); // adj[v] = v번의 친구들for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b); // 서로 친구라 양쪽에 넣어요  adj[b].push(a);} let seen: boolean[] = new Array<boolean>(n + 1).fill(false);const order: number[] = []; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요function dfs(v: number): void {  seen[v] = true;  order.push(v);  for (const w of adj[v]) {    if (!seen[w]) dfs(w);  }} dfs(1);console.log(order.join(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = new Array<boolean>(n + 1).fill(false);let groups: number = 0;for (let s = 1; s <= n; s++) {  if (seen[s]) continue;  groups++;  seen[s] = true;  const stack: number[] = [s];  while (stack.length > 0) {    const v = stack.pop()!;    for (const w of adj[v]) {      if (!seen[w]) {        seen[w] = true;        stack.push(w);      }    }  }}console.log(groups);

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Scanner; public class Main {    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adj.get(v) = v번의 친구들    static boolean[] seen;    static StringBuilder order = new StringBuilder();     // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요    static void dfs(int v) {        seen[v] = true;        order.append(order.length() > 0 ? " " : "").append(v);        for (int w : adj.get(v)) {            if (!seen[w]) dfs(w);        }    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt(), m = sc.nextInt();        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>()); // 빈 목록을 사람마다 하나씩 새로        for (int i = 0; i < m; i++) {            int a = sc.nextInt(), b = sc.nextInt();            adj.get(a).add(b); // 서로 친구라 양쪽에 넣어요            adj.get(b).add(a);        }         seen = new boolean[n + 1];        dfs(1);        System.out.println(order);         // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나        seen = new boolean[n + 1];        int groups = 0;        for (int s = 1; s <= n; s++) {            if (seen[s]) continue;            groups++;            seen[s] = true;            ArrayDeque<Integer> stack = new ArrayDeque<>();            stack.push(s);            while (!stack.isEmpty()) {                int v = stack.pop();                for (int w : adj.get(v)) {                    if (!seen[w]) {                        seen[w] = true;                        stack.push(w);                    }                }            }        }        System.out.println(groups);    }}

using System;using System.Collections.Generic;using System.Linq; class Program{    static List<int>[] adj; // adj[v] = v번의 친구들    static bool[] seen;    static List<int> order = new List<int>();     // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요    static void Dfs(int v)    {        seen[v] = true;        order.Add(v);        foreach (int w in adj[v])        {            if (!seen[w]) Dfs(w);        }    }     static void Main()    {        int[] nm = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();        int n = nm[0], m = nm[1];        adj = new List<int>[n + 1];        for (int v = 0; v <= n; v++) adj[v] = new List<int>(); // 칸마다 빈 목록을 하나씩 새로        for (int i = 0; i < m; i++)        {            int[] ab = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();            int a = ab[0], b = ab[1];            adj[a].Add(b); // 서로 친구라 양쪽에 넣어요            adj[b].Add(a);        }         seen = new bool[n + 1];        Dfs(1);        Console.WriteLine(string.Join(" ", order));         // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나        seen = new bool[n + 1];        int groups = 0;        for (int s = 1; s <= n; s++)        {            if (seen[s]) continue;            groups++;            seen[s] = true;            var stack = new Stack<int>();            stack.Push(s);            while (stack.Count > 0)            {                int v = stack.Pop();                foreach (int w in adj[v])                {                    if (!seen[w])                    {                        seen[w] = true;                        stack.Push(w);                    }                }            }        }        Console.WriteLine(groups);    }}

#include <iostream>#include <vector> std::vector<std::vector<int>> adj; // adj[v] = v번의 친구들std::vector<bool> seen;std::vector<int> order; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요void dfs(int v) {    seen[v] = true;    order.push_back(v);    for (int w : adj[v]) {        if (!seen[w]) dfs(w);    }} int main() {    int n, m;    std::cin >> n >> m;    adj.resize(n + 1);    for (int i = 0; i < m; i++) {        int a, b;        std::cin >> a >> b;        adj[a].push_back(b); // 서로 친구라 양쪽에 넣어요        adj[b].push_back(a);    }     seen.assign(n + 1, false);    dfs(1);    for (size_t i = 0; i < order.size(); i++) std::cout << (i > 0 ? " " : "") << order[i];    std::cout << '\n';     // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나    seen.assign(n + 1, false);    int groups = 0;    for (int s = 1; s <= n; s++) {        if (seen[s]) continue;        groups++;        seen[s] = true;        std::vector<int> stack = {s};        while (!stack.empty()) {            int v = stack.back();            stack.pop_back();            for (int w : adj[v]) {                if (!seen[w]) {                    seen[w] = true;                    stack.push_back(w);                }            }        }    }    std::cout << groups << '\n';}

#include <stdio.h>#include <string.h> #define MAX 101 // 사람은 100명까지라고 정해 둬요 int adj[MAX][MAX], deg[MAX]; // adj[v][0..deg[v]-1] = v번의 친구들int seen[MAX], order[MAX], count = 0; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요void dfs(int v) {    seen[v] = 1;    order[count++] = v;    for (int i = 0; i < deg[v]; i++) {        int w = adj[v][i];        if (!seen[w]) dfs(w);    }} int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int i = 0; i < m; i++) {        int a, b;        scanf("%d %d", &a, &b);        adj[a][deg[a]++] = b; // 서로 친구라 양쪽에 넣어요        adj[b][deg[b]++] = a;    }     dfs(1);    for (int i = 0; i < count; i++) printf(i > 0 ? " %d" : "%d", order[i]);    printf("\n");     // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나    memset(seen, 0, sizeof seen);    int groups = 0, stack[MAX];    for (int s = 1; s <= n; s++) {        if (seen[s]) continue;        groups++;        seen[s] = 1;        int top = 0;        stack[top++] = s;        while (top > 0) {            int v = stack[--top];            for (int i = 0; i < deg[v]; i++) {                int w = adj[v][i];                if (!seen[w]) {                    seen[w] = 1;                    stack[top++] = w;                }            }        }    }    printf("%d\n", groups);    return 0;}

// 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요dfs(v){    seen[v] = 참;    order.넣기(v);    각각 (w 에서 adj[v])    {        만약 (!seen[w])        {            dfs(w);        }    }} nm = 콘솔.수들읽기();n = nm[0];m = nm[1];adj = 새목록(n + 1, []); // adj[v] = v번의 친구들반복 (i = 0; i < m; i++){    ab = 콘솔.수들읽기();    a = ab[0];    b = ab[1];    adj[a].넣기(b); // 서로 친구라 양쪽에 넣어요    adj[b].넣기(a);} seen = 새목록(n + 1, 거짓);order = [];dfs(1);콘솔.쓰기(order.잇기(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = 새목록(n + 1, 거짓);groups = 0;반복 (s = 1; s <= n; s++){    만약 (seen[s])    {        건너뛰기;    }    groups++;    seen[s] = 참;    stack = [s];    동안 (stack.개수 > 0)    {        v = stack[stack.개수 - 1];        stack.자리빼기(stack.개수 - 1);        각각 (w 에서 adj[v])        {            만약 (!seen[w])            {                seen[w] = 참;                stack.넣기(w);            }        }    }}콘솔.쓰기(groups);