ACM 10608 - Friends

#include <stdio.h>
#include <memory.h>
#define SIZE 30000

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, a, b, s, n, m, count, groupID, tmp, replace;
    caseNum = getInt();
    while (caseNum --)
    {
        n = getInt(), m = getInt();
        int friends[n + 1], record[n + 1], max = 0;
        count = 0, groupID = 1;
        memset(friends, 0, sizeof(friends));
        memset(record, 0, sizeof(record));
        while (m --)
        {
            a = getInt(), b = getInt();
            if (friends[a] == 0 && friends[b] == 0)
            {
                friends[a] = groupID, friends[b] = groupID;
                record[groupID] = 2;
                if (max < record[groupID]) max = record[groupID];
                
                groupID ++;
                count ++;
            }
            else if((friends[a] != 0 && friends[b] == 0) ||
                    (friends[a] == 0 && friends[b] != 0))
            {
                tmp = friends[a] < friends[b] ? friends[b] : friends[a];
                friends[a] = tmp, friends[b] = tmp;
                record[tmp] ++;
                if (max < record[tmp]) max = record[tmp];
            } 
            else if (friends[a] != friends[b])
            {
                tmp = friends[b];
                replace = friends[a];
                record[tmp] = 0;
                for (s = 1; s <= n; s ++)
                    if (friends[s] == tmp) friends[s] = replace, record[replace] ++;
                if (max < record[replace]) max = record[replace];
                count --;
            }
            /* for (s = 1; s <= n; s ++)
                printf("%d ", record[s]);
            printf("\n"); */
        }
        printf("%d\n", max);
    }
    
    return 0;
}

回目錄
回首頁