103模 M3P31~M4P42

Public Class Form1                       ‘M3P31 資料結構-是否為樹

    Const MaxN As Integer = 20

    Dim adj(MaxN, MaxN) As Boolean

    Dim nds(MaxN) As Boolean

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

        Me.Hide()

        FileOpen(1, "in1.txt", OpenMode.Input)

        FileOpen(2, "in2.txt", OpenMode.Input)

        FileOpen(3, "out.txt", OpenMode.Output)

        For fn = 1 To 2

            If fn = 2 Then PrintLine(3)

            Dim n As Short = LineInput(fn)

            For k = 1 To n

                Dim s As String = LineInput(fn)

                PrintLine(3, m3p31(s))

            Next

        Next

        End

    End Sub

    Function m3p31(ByVal s As String) As String

        m3p31 = "T"

        ttrim(s, "  ", " ") : ttrim(s, ", ", ",") : ttrim(s, " ,", ",")   ‘2空轉1空、 去逗後空、 去逗前空

        Dim egs() = s.Split(" ")

        Dim egcnt As Integer = egs.Length  '邊數

        Dim st As Integer  ' dfs的起點

        Array.Clear(adj, 0, MaxN * MaxN) : Array.Clear(nds, 0, MaxN)

        For i = 0 To egcnt - 1

            Dim xy() = egs(i).Split(",")

            Dim x As Integer = xy(0), y As Integer = xy(1)

            adj(x, y) = True : adj(y, x) = True

            nds(x) = True : nds(y) = True

            st = x

        Next

        Dim ndcnt As Integer = 0  '節點數

        For i = 0 To MaxN

            If nds(i) Then ndcnt += 1

        Next

        If ndcnt <> egcnt + 1 Then

            Return "F"

        Else

            dfs(st)

            For i = 0 To MaxN

                If nds(i) Then Return "F" '有節點未訪

            Next

        End If

    End Function

    Sub dfs(ByVal st As Integer)

        nds(st) = False  '訪過 註銷

        For v = 0 To MaxN

            If nds(v) And adj(st, v) Then dfs(v)

        Next

    End Sub

    Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)           ‘將a 取代為 b

        Do Until InStr(s, a) = 0

            s = s.Replace(a, b)

        Loop

    End Sub

End Class

Public Class Form1              ‘M3P32 資料結構-樹葉節點到根節點之路徑

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

        FileOpen(1, "in1.txt", OpenMode.Input)

        FileOpen(2, "in2.txt", OpenMode.Input)

        FileOpen(3, "out.txt", OpenMode.Output)

        For fn = 1 To 2

            If fn=2 Then PrintLine(3)

            Dim n As Integer = LineInput(fn)

            For i = 1 To n

                If i > 1 Then LineInput(fn)

                Dim nds As Integer = LineInput(fn)

                Dim par(100) As Integer   '父是誰

                Dim chi(100) As Boolean   '是否有子？

                For j = 1 To nds

                    Dim xy() = LineInput(fn).Split(",")

                    Dim x As Integer = xy(0), y As Integer = xy(1)

                    par(x) = y     ' x 的父是 y

                    chi(y) = True  ' y 有子

                Next

 Rem 以下為測試用多印的

                For j = 0 To nds - 1  '印各節點的父，是否有子？

                    Print(3, j & ": " & par(j) & " :" & IIf(chi(j), "Y", "N") & "  ")

                Next

                PrintLine(3)

Rem 以上為多印的

                For j = 0 To nds - 1

                    If Not chi(j) Then  ‘沒有兒子即是葉節點

                        Dim cnt = 0

                        Dim s As String = ""

                        Dim p = par(j)

                        Do Until par(p) = 99

                            If cnt > 0 Then s &= ("," & p) Else s &= p

                            cnt += 1

                            p = par(p)

                        Loop

                        If cnt > 0 Then s = "{" & s & "}" Else s = "N"

                        PrintLine(3, j & ":" & s)

                    End If

                Next

            Next

        Next

        End

    End Sub End Class