29ος ΠΔΠ Γ' Φάση: Οδικό δίκτυο (villages) - Λύση

Επεξήγηση εκφώνησης

Παρατήρηση 1: Κάθε φορά που βάζουμε μία ακμή, μειώνουμε τις συνολικές ομάδες κατά μία ή καμία.

Απόδειξη: Οι κόμβοι που συνδέει η ακμή μπορεί είτε να ανήκουν στην ίδια ομάδα είτε όχι. Αν ανήκουν σε διαφορετική ομάδα τότε προσθέτοντας την ακμή οι δύο ομάδες γίνονται μία. Αν ανήκουν στην ίδια ομάδα, τότε δεν αλλάζει κάτι.

Παρατήρηση 2: Δεν έχει σημασία ποιες ομάδες ενώνουμε.

Συνεπώς, σημασία έχει μόνο πόσες διαφορετικές ομάδες (\(\mathit{groups}\)) υπάρχουν στην αρχή. Αν \(\mathit{groups} > Κ\) τότε μπορούμε μπορούμε να ενώνουμε μόνο κόμβους διαφορετικών ομάδων και στο τέλος να μείνουν \(\mathit{groups} - K\). Αν \(K \geq \mathit{groups}\) τότε μπορούμε να ενώσουμε όλες τις ομάδες σε μία με τον ίδιο τρόπο.

Παρακάτω παρουσιάζουμε δύο λύσεις για να μετρήσουμε τις διαφορετικές ομάδες. Και στις δύο κάνουμε αναζήτηση κατά βάθος (DFS), αλλά διαφέρει ο τρόπος που αναπαριστούμε τον γράφο.

Λύση με πίνακα γειτνίασης

Ο πίνακας γειτνίασης αναπαριστά έναν γράφο ως έναν δισδιάστατο πίνακα \(\mathit{adj}\) από booleans, όπου \(\mathit{adj}[i][j]\) δείχνει αν οι κόμβοι \(i\) και \(j\) είναι συνδεδεμένοι ή όχι.

Για το αρχείο εισόδου 2, ο πίνακας είναι

Έχοντας τον γράφο σε αυτή την αναπαράσταση, ξεκινάμε από κάθε κόμβο που δεν έχουμε επισκεφτεί και μαρκάρουμε όλους τους κόμβους που επισκεπτόμαστε. Κάθε φορά που ξεκινάμε από κόμβο που δεν έχουμε επισκεφτεί, ξεκινάει καινούργια ομάδα.

Αφού επισκεφτούμε όλους τους κόμβους και αφού υπολογίσουμε το \(\mathit{groups}\), τότε χρησιμοποιούμε την συνθήκη που αναφέραμε παραπάνω.

Ο αλγόριθμος αυτό θα επεξεργαστεί κάθε κόμβο μία φορά και για αυτόν θα διατρέξει όλους τους κόμβους ώστε να βρει τους γειτονικούς του. Άρα η πολυπλοκότητά του είναι \(\mathcal{O}(N^2)\) και χρειάζεται \(\mathcal{O}(N^2)\) μνήμη.

#include <algorithm>
#include <cstdio>

// Στοχεύουμε μόνο για το 50%.
const size_t MAXN = 10000;

bool adj_matrix[MAXN + 1][MAXN + 1];
bool visited[MAXN + 1];

long N, M, K;

void visit(long n) {
  visited[n] = true;
  // Διατρέχουμε όλους τους κόμβους.
  for (long i = 1; i <= N; ++i) {
    // Αν συνδέεται ο n με τον i και δεν τον έχουμε επισκεφτεί,
    // τότε τον επισκεπτόμαστε.
    if (adj_matrix[n][i] && !visited[i]) {
      visit(id);
    }
  }
}

int main() {
  FILE *fi = fopen("villages.in", "r");
  fscanf(fi, "%ld %ld %ld", &N, &M, &K);
  
  for (long i = 0; i < M; ++i) {
    long A, B;
    fscanf(fi, "%ld %ld", &A, &B);
    adj_matrix[A][B] = 1;
    adj_matrix[B][A] = 1;
  }
  fclose(fi);
  
  // Μετράμε τις διαφορετικές ομάδες που υπάρχουν.
  long groups = 0;
  for (long i = 1; i <= N; ++i) {
    if (!visited[i]) {
      ++groups;
      visit(i);
    }
  }
  
  FILE *fo = fopen("villages.out", "w");
  fprintf(fo, "%ld\n", std::max(1L, groups - K));
  fclose(fo);
  return 0;
}

Λύση με λίστα γειτνίασης

Ο πίνακας γειτνίασης χρειάζεται πολύ μνήμη και είναι αργή η εύρεση των γειτονικών στοιχείων. Η λίστα γειτνίασης κρατάει για κάθε κόμβο \(n\) μία λίστα (ή ένα vector) μόνο από τους συνδεδεμένους κόμβους. Άρα κάθε φορά που επισκεπτόμαστε έναν κόμβο διατρέχουμε τη λίστα για να επισκεφτούμε τους γείτονες του, που δεν είχαμε επισκεφτεί.

Συνολικά θα επισκεφτούμε κάθε κόμβο μία φορά και θα διατρέξουμε δύο φορές κάθε ακμή. Συνεπώς η πολυπλοκότητα είναι \(\mathcal{O}(N + M)\) και η μνήμη \(\mathcal{O}(N+M)\).

#include <algorithm>
#include <cstdio>
#include <vector>

const size_t MAXN = 1000000;

std::vector<long> adj_list[MAXN + 1];
bool visited[MAXN + 1];

long N, M, K;
 
void visit(long n) {
  visited[n] = true;
  // Διατρέχουμε όλους τους κόμβους.
  for (const auto& neighbour : adj_list[n]) {
    if (!visited[neighbour]) {
      visit(neighbour);
    }
  }
}

int main() {
  FILE *fi = fopen("villages.in", "r");
  fscanf(fi, "%ld %ld %ld", &N, &M, &K);
  
  for (long i = 0; i < M; ++i) {
    long A, B;
    fscanf(fi, "%ld %ld", &A, &B);
    adj_list[A].push_back(B);
    adj_list[B].push_back(A);
  }
  fclose(fi);
  
  // Μετράμε τις διαφορετικές ομάδες που υπάρχουν.
  long groups = 0;
  for (long i = 1; i <= N; ++i) {
    if (!visited[i]) {
      ++groups;
      visit(i);
    }
  }

  FILE *fo = fopen("villages.out", "w");
  fprintf(fo, "%ld\n", std::max(1L, groups - K));
  fclose(fo);
  return 0;
}

Iterative λύση

Παρόλο που ο αλγόριθμος είναι θεωρητικά βέλτιστος, η αναδρομική κλίση της συνάρτησης visit μπορεί να δημιουργήσει μεγάλη στοίβα κλίσεων και να οδηγήσει σε stack overflow. Για να το αποφύγουμε αυτό μπορούμε να χρησιμοποιήσουμε μία κανονική στοίβα στη C++, όπου προσθέτουμε τους κόμβους για να επισκεφθούμε.

void visit(long n) {
  std::vector<long> st;
  st.push_back(n);
  
  while (!st.empty()) {
    long n = st.back();
    st.pop_back();
    for (const auto& neighbour : adj_list[n]) {
      if (!visited[neighbour]) {
        visited[neighbour] = true;
        st.push_back(neighbour);
      }
    }
  }
}