Problem 10583 Ubiquitous Religions，最大宗教群

此題與 Problem 10608 Friends 是一樣的，不過數量更大，建議可以使用輸入優化來縮短時間，但還是跑了一秒多，說明可點上面連結去看。

以下還是提供 C 語言程式碼：

int n, m;

int getInt()
{
    char ch;
    int n = 0;
    while( ch = getchar())
        if(ch != ' ' && ch != '\n') break;
    n = ch - 48;
    while( ch = getchar())
    {
        if(ch == ' ' || ch == '\n') break;
        n = n * 10 + ch - 48;
    }
    return n;
}

主程式內 ....
while ((n = getInt()) && (m = getInt()))
{
    int student[n + 1];
    religionID = 1, count = 0;
    memset(student, 0, sizeof(student));
    while (m --)
    {
        i = getInt(), j = getInt();
        if (student[i] == 0 && student[j] == 0)
        {
            student[i] = religionID, student[j] = religionID;
            religionID ++;
            count ++;
        }
        else if((student[i] != 0 && student[j] == 0) ||
                (student[i] == 0 && student[j] != 0))
        {
            tmp = student[i] < student[j] ? student[j] : student[i];
            student[i] = tmp, student[j] = tmp;
        } 
        else if (student[i] != student[j])
        {
            tmp = student[j];
            replace = student[i];
            for (s = 1; s <= n; s ++)
                if (student[s] == tmp) student[s] = replace;
            count --;
        }
    }
    /* for (i = 1; i <= n; i ++)
        printf("%d ", student[i]);
    printf("\n"); */
    for (i = 1; i <= n; i ++)
        if (student[i] == 0) count ++;
    printf("Case %d: %d\n", caseNum ++, count);
}

By David.K

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