/************************************************ Grundlegende Algorithmen mit Java, http://algorithmen-und-problemloesungen.de/ Copyright @2007-2008 by Doina Logofatu in C#: Michael Gärtner ************************************************/ using System; using System.IO; namespace Logofatu { public class P02MapColoring { private static String FileInputName = "map.in"; private static String FileOutputName = "colors.out"; static void Main(string[] args) { StreamReader sr = null; StreamWriter sw = null; try { sr = new StreamReader(FileInputName); sw = new StreamWriter(FileOutputName); // Daten einlesen int n = int.Parse(sr.ReadLine()); int[][] a = new int[n][]; for ( int i = 0; i < n; i++ ) { a[i] = new int[n]; string[] sArray = sr.ReadLine().Split(' '); for ( int j = 0; j < n; j++ ) { a[i][j] = int.Parse(sArray[j]); } } // Algorithmus int[] col = new int[n]; col[0] = 0; for ( int i = 1; i < n; i++ ) { int j = -1; bool ok = false; do { j++; ok = true; for ( int k = 0; ok && k < i; k++ ) { if ( 1 == a[k][i] && col[k] == j ) { ok = false; break; } } } while ( !ok ); col[i] = j; } // Ausgabe for ( int i = 0; i < n; i++ ) { sw.Write(col[i] + 1); sw.Write(" "); } } catch ( IOException ) { Console.WriteLine("Fehler bei der Dateiverarbeitung!"); } finally { if ( sr != null ) { sr.Close(); } if ( sw != null ) { sw.Close(); } } } } }