26ος ΠΔΠ Α' Φάση: Δομές κοινωνικής αλληλεγγύης (domes) - Λύση

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

Σε αυτό το πρόβλημα δίνεται ένας γράφος με κόμβους τις οργανώσεις και ακμές τις συνδέσεις μεταξύ των οργανώσεων. Για το πρώτο παράδειγμα, ο γράφος είναι ο εξής:

Οι μοναδικοί κόμβοι με λιγότερες από δύο συνδέσεις είναι ο κόμβος \(2\) και ο κόμβος \(6\).

Η εκφώνηση μας ζητάει να μετρήσουμε το πλήθος αυτών των κόμβων. Είναι ξεκάθαρο ότι ένας κόμβος έχει λιγότερες από δύο συνδέσεις όταν εμφανίζεται σε λιγότερα από δύο ζεύγη ακεραίων στο αρχείο εισόδου.

Λύση

Καθώς διαβάζουμε τα ζεύγη ακεραίων διατηρούμε:

• \(\mathit{count}[v]\): σε πόσα ζεύγη εμφανίζεται ο κόμβος \(v\). Αρχικά \(0\).
• \(\mathit{answer}\): πόσοι κόμβοι εμφανίζονται σε λιγότερες από δύο συνδέσεις. Αρχικά \(N\), καθώς κανένας κόμβος δεν έχει συνδέσεις.

Για κάθε ζεύγος \((A, B)\) αυξάνουμε το \(\mathit{count}[A]\) και το \(\mathit{count}[B]\) κατά ένα. Κάθε φορά που το \(\mathit{count}[v]\) γίνεται \(2\), μειώνουμε το \(\mathit{answer}\), αφού πλέον ο κόμβος \(v\) έχει τουλάχιστον δύο συνδέσεις.

Αφού διαβάσουμε όλο το αρχείο εισόδου, η απάντηση είναι στη μεταβλητή \(\mathit{answer}\).

#include <cstdio>

const size_t MAXN = 100'000;

long count[MAXN];

int main() {
   FILE *fi = fopen("domes.in", "r");
   long N, M;
   fscanf(fi, "%ld %ld", &N, &M);
   long answer = N;
   for (long i = 0; i < M; ++i) {
      long A, B;
      fscanf(fi, "%ld %ld", &A, &B);
      ++count[A];
      ++count[B];
      if (count[A] == 2) --answer;
      if (count[B] == 2) --answer;
   }
   fclose(fi);
  
   FILE *fo = fopen("domes.out", "w");
   fprintf(fo, "%ld", answer);
   fclose(fo);
   return 0;
}
 

Ο αλγόριθμος χρειάζεται \(\mathcal{O}(N+M)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.

Σημείωση: Τα αρχεία εισόδου δεν είχαν πολλαπλές φορές το ίδιο ζεύγος (πχ “2 4” και “4 2”). Αν μπορούσαν να το έχουν, τότε πρέπει μαζί με το \(\mathit{count}\) να κρατάμε για τους κόμβους με μία σύνδεση, τον κόμβο με τον οποίο συνδέονται. Έτσι όταν έρθει η δεύτερη σύνδεση, μπορούμε να ελέγξουμε αν είναι διαφορετική.