Aylık Programlama Sorusu - Ekim 2008

Tüm Sorularımız

Aylık programlama sorumuza gösterdiğiniz ilgi için öncelikle bütün okurlarımıza teşekkür ederiz. Aydan aya artan ilginiz ile Eyül ayını da geride bırakırken, sizler için, gönderilen cevaplar içinden çözüm açısından en uygun olanı seçtik. Eylül ayı sorusunda, hem kodun verimliliği hem de anlaşılabilirliği dikkate alındığında, en iyi çözümü yollayan arkadaşımız Sayın Umut Öztok'u kutluyoruz. İsterseniz siz de kendisinin çözümüne göz atabilirsiniz. Bu ayın yeni sorusu ise aşağıda açıklanmıştır. Ayrıca, sorunun PDF sürümünü de bilgisayarınıza indirebilirsiniz.

Aylık programlama sorumuz için izlenecek yöntemi hatırlatmakta yarar var: Her ayın 1'inde dergimizle birlikte yayınlanacak sorumuzun cevaplarını, aynı ayın 20'sine kadar gönderebileceksiniz. Çözümler C/C++/Java dillerinde yazılmış olup, ayliksoru@cclub.metu.edu.tr adresine gönderilmesiyle elimize ulaşacak. En verimli ve en doğru çözümü gönderen okuyucularımız bir sonraki ay aynı sayfada duyurulacak ve bazı kod örnekleri de beraberinde yayınlanacak. Ayrıca, aylık sorularımıza gösterdiğiniz ilgiye karşı, bu aydan itibaren artık sizlerden gelen yanıtların değerlendirilmesi sonucu aylık sorumuza en iyi cevabı gönderen arkadaşlara çeşili armağanlarımız olacak! Her türlü sürpriz gelişme için, dergimizi düzenli olarak takip edin. Hepinize şimdiden kolay gelsin :)

İNTERNET

Ülke sakinlerine doyumsuz internet keyfi yaşatmak isteyen Akkuş Ülkesi’nin taçsız kralı, hizmet insanı Yiğit Akkuş teknoloji gurusu pek güzel insan Sn. Gökhan Tüysüz önderliğindeki araştırma grubuyla daha ucuz ve daha hızlı internet bağlantısını ülkesine nasıl getirebileceğine dair toplantılar yapar. Ülkenin var olan altyapısını inceleyen Gökhan Tüysüz ve grubu ülkenin bazı merkezlerine uydu yerleştirirlerse var olan altyapı ile çok daha hızlı internet hizmeti verebileceklerini krala iletir. Fakat sorun şudur: Uydular çok pahalıdır. Bu yüzden her merkeze uydu yerleştirmek mümkün değildir. Yoğun bir çalışmadan sonra Gökhan Tüysüz ve grubu uyduları koyacakları yerleri belirlemek için bir fikir geliştirirler. Ülkeyi bölgelere ayıracaklar ve her bölgeye bir uydu koyacaklardır. Kural ise şudur: Bir bölgedeki herhangi bir şehrin aynı bölge içindeki diğer tüm şehirlere var olan kablolar vasıtasıyla bağlı olması gerekmektedir. Akkuş ülkesi binlerce şehir içerdiğinden, bölgelerin nasıl ayıracağına kolayca karar verilememektedir. Sizden beklediğimiz ülkeyi yukarıdaki özelliği taşıyan en az sayıda bölgeye ayrıran programı yazmanız.

Varsayımlar:

Şehir sayısı N’dir. ( 2 < N < 5000 )
Kablolar tek yönlüdür. 2 yöne birden iletim yapmak için kullanılmamaktadırlar.
Bir şehrin diğer bir şehre bağlı olması için aralarında direkt bağlantı olması şart değildir. Yani A B’ye bağlıysa B de C’ye bağlıysa A C’ye bağlı demektir.
A’nın B şehrine bağlı olması B’nin A şehrine bağlı olduğu manasına gelmez.
Şehir isimleri pozitif tamsayılardan oluşan şehir koduyla belirilecektir.
Şehir kodları ülkedeki toplam şehir sayısından küçüktür. ( 0 < M ≤ N )

Girdi(internet.gir):

Girdinin ilk satırında şehir sayısı ve ilk satır hariç girdinin toplam kaç satır olduğu verilecektir.
Sonraki her bir satırda sırasıyla hangi şehirden hangi şehre kablo çekili olduğu verilecektir.

Çıktı(internet.cik):

Çıktının ilk satırına ülkenin en az kaç bölgeye ayrılabileceğini yazmalısınız.
Sonraki her satıra her bölgenin içerdiği şehirlerin şehir kodunu yazacaksınız.
Bölgelerin bastırılma sırası ya da şehir sıraları belli bir kurala bağlı değildir.

Örnek:

internet.gir
8 13
1 2
2 3
3 4
4 3
4 8
3 7
2 6
5 1
2 5
5 6
6 7
7 6
7 8

internet.cik
4
1 2 5
6 7
8
3 4

Eray Molla

Bu derginin içeriği, Creative Commons lisansı ile korunmaktadır.
Kaynak göstermek ve link vermek şartıyla ticari olmayan amaçlarla yazılarımızı kullanabilirsiniz.