Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
tvboy
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 99
#1

Написать программу Изолированные города(Описание внутри) - C++

25.04.2013, 02:46. Просмотров 577. Ответов 3
Метки нет (Все метки)

В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве.

Формат входного файла

Во входном файле записаны сначала два числа N и M, задающие соответственно количество городов и количество дорог (1≤N≤100, 0≤M≤1000), а затем перечисляются попарно связанные дорогами города. Каждая дорога задается номерами городов, которые она соединяет.

Формат выходного файла

В выходной файл выведите одно число – количество штатов в государстве
.

Примеры:

input.txt 6 3 1 3 1 5 2 6 output.txt 3
input.txt 7 0 output.txt 7

 Комментарий модератора 
Запрещено размещать тему в нескольких разделах одновременно (кросспостинг), а также дублировать тему в одном разделе.
Правила форума
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 02:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Написать программу Изолированные города(Описание внутри) (C++):

Написать программу на языке С++, содержащую объявление и описание дружественных структур - C++
Всем добрый вечер, помогите разобраться с заданием, а именно как лучше сделать. И если не сложно, подскажите как реализовать программу...

задача ШКОЛЫ (описание внутри) - C++
Школы С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для...

Ошибка описание внутри темы - C++
#include <stdio.h> #include <conio.h> #include <math.h> #include <iostream> int main (void) { setlocale(LC_ALL, "Russian");...

Расстояние от точки до луча (описание внутри) - C++
Помогите люди добрые :) Расстояние от точки до луча Даны координаты точки (x,y) и координаты начала и конца вектора (x1,y1) и (x2,y2). ...

Найти количество всевозможных маршрутов от города до города - C++
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до...

Составить программу которая на введенную дату выдает название города - C++
Мы с вами знаем, что Санкт-Петербург менял свое название несколько раз. Составить программу которая на введенную дату выдает название...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
25.04.2013, 08:31 #2
вам нужно найти количество компонент связности. Дфсом делается.
0
Shef4u
15 / 15 / 0
Регистрация: 31.10.2011
Сообщений: 116
01.05.2013, 18:36 #3
ну и? вроде как не такая и сложная задача. Только надо бы во входном файле отделять количество городов, дорог и пары разными знаками (кома, дефис и т.д.) чтобы в цикле когда будешь с файла считывать в условии if () прописать до какого знака считывать. Правда с одним числом будет проще чтобы перевести его из строки в число, а вот если 2 числа с пробелом то надо будет либо убирать пробелы либо не знаю даже, записать в массив вместе с пробелом и брать тогда с него 0 и 2 элементы. как-то так
0
tvboy
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 99
16.05.2013, 02:27  [ТС] #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#define CITY_MAX   100
#define ROAD_MAX   1000
struct road
{
  int city1;
  int city2;
};
struct roadto
{
  struct roadto *next;
  int city;
};
struct city
{
  struct roadto *roads;
  int state;
};
void assignCity( struct city *cityList, struct city *city, int state)
{
  struct roadto *roadto;
  city->state = state;
  for( roadto = city->roads; roadto != NULL; roadto = roadto->next)
    if( cityList[roadto->city].state == 0 )
      assignCity( cityList, &cityList[roadto->city], state);
}
int main( void )
{
// in order to not alloc memory
  struct roadto roadHeap[2*ROAD_MAX];
  struct city cities[CITY_MAX+1];  // skipping city number 0
// some variables
  int stateCount = 0;
  int r, c;
// supposedly from data file, correct values
  int N = 6;
  int M = 3;
  struct road roadList[ROAD_MAX] = { { 1, 3}, { 1, 5}, { 2, 6} };
// Initing city list
  for( c = 1; c <= N; c++)
  {
    cities[c ].roads = NULL;
    cities[c ].state = 0; // not assigned
  }
// Linking cities with road list
  for( r = 0; r < M; r++)
  {
    struct road *road = &roadList[r];
    struct roadto *roadto;
    // city1 -> city2
    roadto = &roadHeap[2*r]; // instead of malloc
    roadto->city = road->city2;
    roadto->next = cities[road->city1].roads;
    cities[road->city1].roads = roadto;
    // city2 -> city1
    roadto = &roadHeap[2*r+1]; // instead of malloc
    roadto->city = road->city1;
    roadto->next = cities[road->city2].roads;
    cities[road->city2].roads = roadto;
  }
#if 0
// Checking links
  for( c = 1; c <= N; c++)
  {
    struct roadto *roadto;
    printf( "city #%d:", c);
    for( roadto = cities[c ].roads; roadto != NULL; roadto = roadto->next)
      printf( " %d", roadto->city);
    printf( "\n" );
  }
#endif
// Assigning cities
  for( c = 1; c <= N; c++)
    if( cities[c ].state == 0 )
    {
      ++stateCount;
      assignCity( cities, &cities[c ], stateCount);
    }
// Wanted result
  printf( "State count: %d\n", stateCount);
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2013, 02:27
Привет! Вот еще темы с ответами:

Для заданной вершины p найти маршруты в другие города, хотя бы один маршрут для каждого города - C++
Добрый день мои дорогие и многоуважаемые форумчане. Прошу вашей помощи: Вот дали задание в университете: Для заданной вершины p найти...

Написать модуль, содержащий описание класса Дата - C++
Написать модуль, содержащий описание следующего класса (использовать private и public) / C# Объект - дата этого года. Свойства -...

Нужно по коду написать описание как на примере - C++
Вот пример описания: Вначале программы зададим две переменные (LENG и LENN) с размерами 6 и 15, для дальнейшего удобного использования в...

Проверка корректности введенного города игра "Города" - C++
Здравствуйте, пишу программку &quot;Города&quot;, т.е. пользователь называет какой-нибудь город, допустим, &quot;Омск&quot;. Компьютер считывает последнюю...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.05.2013, 02:27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru