fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 28943 (C++) В поисках неизведанного
최초 업로드: 2025-11-14 13:19:05
최근 수정 시간: 2025-11-14 13:19:05
게시자: rlatjwls3333
카테고리: 백준
조회수: 5
# [Bronze I] В поисках неизведанного [문제 링크](https://www.acmicpc.net/problem/28943) ## 문제 설명 <p>Диппер и Мэйбл решили еще раз обследовать Гравити Фолз. Надо сказать, что Гравити Фолз не сильно отличается по общему устройству от других городов --- он также представляет из себя совокупность домов, соединенных улицами. Причем для каждой пары домов существует не более одной улицы их соединяющей. Да и петель, то есть улиц, соединяющих дом с самим собой, тоже нет. Также известно, что если по улице можно добраться от дома А до дома В, то и от дома В до дома А можно добраться по этой же улице.</p> <p>Сейчас Диппер и Мэйбл решили составить список маршрутов, которые бы посещали каждый дом ровно один раз. (То есть если в городе $n$ домов, то в маршруте будет ровно $n$ различных чисел --- номеров домов, и между любыми двумя соседними будет существовать одна улица). Диппер и Мэйбл считают два маршрута разными, если в них разные последовательности домов.</p> <p>Список оказался довольно большим. К тому же Диппер и Мэйбл не уверены, что он правильный. Для того чтобы проверить выкладки, они хотели бы для начала знать количество таких путей. Без Вас им точно не обойтись! </p> ## 입력 <p>В первой строке входного файла дано натуральное число $n$ --- количество домов ($1 \le n \le 1000$). Далее следуют $n$ строк. Каждая $i$-ая строка задана в следующем формате: первое число в строке $k$ --- число соседних (то есть связанных улицей) домов для $i$-го дома, далее перечислены $k$ различных чисел --- номера соседних с $i$-ым домов. </p> ## 출력 <p>Выведите одно число --- количество вышеописанных маршрутов. Поскольку данное число может быть довольно большим, выведите его по модулю $2$.</p> ## 풀이 해밀턴 거리는 모든 정점을 지나는 순서의 경우의 수이다. - 정점이 하나인 경우는 자기 자신을 방문하는 경우 1개밖에 없으니 1을 출력한다. - 정점의 개수가 2 이상이면 어느 경로와 그 경로를 완전히 뒤집은 경로가 존재하므로 항상 2의 배수로 나와 0을 출력한다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout << (n==1); } ```