Problem 459 Graph Connectivity，畫連接線

此題要用到回溯演算法，讀入第一個英文字母後，決定陣列的範圍，我們可以宣告整數陣列為 W[27][27]，因為大寫字母最大到 Z(26)，再接下來有 0 到多行，每行都有兩個大寫英文 ch1 和 ch2，代表連接線，此時我們可以改變 W 陣列內的值，將 W[ch1 - 'A'][ch2 - 'A'] = W[ch2 - 'A'][ch1 - 'A'] = 1，因為連接線是無向的，也藉此表示這兩點有連接。

再來宣告一整數陣列 v[27]，紀錄每個連結點是否有拜訪過，一旦拜訪，就不再拜訪，當拜訪每一個節點，改變它在 v 陣列位置的值為 1。接著再找尋它每一個能連結的點，就再將它每個能連結點 v 陣列位置的值改為 1，再繼續找尋這些連結點能連結的點。如此如此做下去，結果就會出來了。

以下為拜訪函式：

int m;
int W[27][27];
int v[27];
void visit(int n)
{
     v[n] = 1;
     int i, j;
     for (i = 0; i <= m; i ++)
         if (v[i] == 0 && W[n][i] == 1)
             visit(i);
}

在主程式如此呼叫此函式：

int n, i, j;
char ch[3];
scanf("%d", &n);
for (j = 0; j < n; j ++)
{
    int count = 0, isCase = 0;  
    memset(v, 0, sizeof(v));
    memset(W, 0, sizeof(W));
    while (gets(ch))
    {
        int len = strlen(ch);
        if (len == 0) 
        { 
           if (isCase)
           {
               for (i = 0; i <= m; i ++)
               {
                   if (v[i] == 0)
                       visit(i), count ++;
               }
               if (j != 0) printf("\n");
               printf("%d\n", count);
               isCase = 0;
               break;
           } 
        }
        if (len == 1) isCase = 1, m = ch[0] - 'A';
        if (len > 1)
        {
            int node1 = ch[0] - 'A';
            int node2 = ch[1] - 'A';
            W[node1][node2] = W[node2][node1] = 1;
        }
    }
    if (isCase)
    {
        for (i = 0; i <= m; i ++)
        {
            if (v[i] == 0)
                visit(i), count ++;
        }
        if (j != 0) printf("\n");
        printf("%d\n", count);
        isCase = 0;
    }
}

By David.K

p459題目連結
回ACM題庫目錄
回首頁