2010年6月18日 星期五

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題庫目錄
回首頁

沒有留言: