2010年9月17日 星期五

ACM 10583 - Ubiquitous Religions

#include <stdio.h>
#include <memory.h>
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;
}

int main()
{
int caseNum = 1, s, i, j, religionID, count, tmp, replace;
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);

}
return 0;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...