А вот соответственно сама задача:
государстве 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
| Код |
#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);
}
|
|