Форум программистов [Powered by Invision Power Board]

Код

#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);
}