İki Parçalı mı?
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 14 / 14.
Bir graf, düğümlerini her kenar bir gruptaki bir düğümü diğer gruptaki bir düğüme bağlayacak şekilde iki gruba ayırabiliyorsanız iki parçalıdır (bipartite). Kırmızı ve mavi olarak düşünün: her kenarın bir kırmızı uç noktası ve bir mavi uç noktası vardır.
BFS temiz bir test sunar. Herhangi bir düğümden başlayın, onu kırmızıya boyayın ve dışa doğru ilerleyin. Her yeni komşu, geldiğimiz düğümün zıt rengini alır. Eğer aynı renge sahip iki düğümü birbirine bağlayan bir kenar görürsek, graf iki parçalı değildir. Klasik engel tek uzunluklu bir döngüdür: bir 0-1-2-0 üçgeni, 0 düğümünü hem kırmızı hem de mavi olmaya zorlar.
Unutulmaması gereken bir şey: Eğer grafın birden fazla bağlantılı bileşeni varsa, her biri üzerinde yeni bir 2-boyama başlatmanız gerekir. En kolay yöntem, boyanmamış bir düğüm bulduğunda bir BFS başlatan, tüm düğümler üzerinde dönen tek bir döngüdür.
Görev
KolayBir 2D tam sayı dizisi adjacency ve bir tam sayı dizisi vertices alan ve eğer grafik iki parçalı (bipartite) ise true, aksi takdirde false döndüren bir isBipartite fonksiyonu yazın.
Grafiği oluşturun (her biri için addVertex, ardından her biri için addEdge kullanın). Daha sonra her bağlı bileşen üzerinde BFS aracılığıyla 2-renklendirme yapın: başlangıç rengini 0 olarak atayın, her komşuya 1 - color[u] rengini verin. Eğer her iki uç noktasının da zaten aynı renge sahip olduğu bir kenar bulursanız, false döndürün. Aksi takdirde true döndürün.
Graph sınıfını kullanmalısınız (graph içinde sağlanmıştır) - komşulukları modellemek için dilin yerleşik yapılarını (map'ler, set'ler) kullanmayın. Algoritma için yardımcı veriler (renk haritası, kuyruk) standart kütüphane tiplerini kullanabilir.
Kendin dene
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}