Informatika gyűjtemény

Egy szinttel feljebb Halozat.cs

2004050607080910

<<  12. óra  >>

<<  Hálózat  >>

NézetNyomtat

Halozat.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
using System;
using System.IO;
using System.Collections.Generic;

namespace Halozat
{
    class Halozat
    {
        // N = csomópontok száma
        // M = kapcsolatok száma
        // K = kérdéses csomópont
        private int m;
        private byte n, k;
        
        // itt tároljuk, hogy x-ből y-ba van-e út.
        private bool[,] edges;
        
        public Halozat()
        {
            StreamReader ins = new StreamReader("halozat.be");
            string[] line = ins.ReadLine().Split(' ');
            n = Byte.Parse(line[0]);
            m = Int32.Parse(line[1]);
            k = (byte)(Byte.Parse(line[2])-1); // id-t tároljuk
            
            edges = new bool[n,n];
            for( int i=0; i<n; i++ ) {
                for( int j=0; j<n; j++ ) {
                    edges[i,j] = false;
                }
            }
            
            for( int i=0; i<m; i++ ) {
                line = ins.ReadLine().Split(' ');
                edges[ Int32.Parse(line[0])-1 , Int32.Parse(line[1])-1 ] = true;
            }
            
            byte[] res = walkFromK();
            StreamWriter outs = new StreamWriter("halozat.ki");
            outs.WriteLine(res.Length);
            for( int i=0; i<res.Length; i++ ) {
                if( i!=0 ) outs.Write(" ");
                outs.Write(res[i]+1);
            }
            outs.Close();
        }
        
        private byte[] walkFromK()
        {
            // először bejárjuk K-ból, és megnézzük, hogy kit érünk el -> A
            // utána megint K-ból járjuk be, de már a visszafele utakon megyünk. -> B
            // A\B-t keressük.
            
            Queue<byte> queue = new Queue<byte>(n);
            List<byte> stash = new List<byte>(n);
            bool[] wasThere = new bool[n];
            for( int i=0; i<n; i++ ) {
                wasThere[i] = false;
            }
            
            queue.Enqueue(k);
            wasThere[k] = true;
            
            // először bejárjuk K-ból, amit megtalálunk azt elmentjük
            byte node;
            while( queue.Count > 0 ) {
                node = queue.Dequeue();
                for( byte i=0; i<n; i++ ) {
                    if( edges[node, i] && !wasThere[i] ) {
                        stash.Add(i);
                        queue.Enqueue(i);
                        wasThere[i] = true;
                    }
                }
            }
            
            queue.Enqueue(k);
            for( int i=0; i<n; i++ ) {
                wasThere[i] = false;
            }
            wasThere[k] = true;
            
            // megint bejárjuk, de K-ból, viszont a fordított éleken megyünk
            // az így találtakat kiveszük, mert ők nem kellenek.
            while( queue.Count > 0 ) {
                node = queue.Dequeue();
                for( byte i=0; i<n; i++ ) {
                    if( edges[i, node] && !wasThere[i] ) {
                        stash.Remove(i);
                        queue.Enqueue(i);
                        wasThere[i] = true;
                    }
                }
            }
            
            stash.Sort();
            return stash.ToArray();
        }
        
        public static void Main(string[] args)
        {
            new Halozat();
        }
    }
}
(Vissza)