您當(dāng)前位置：首頁 > php開源 > php教程 > 網(wǎng)易游戲面試題 - 誰收到了消息

網(wǎng)易游戲面試題 - 誰收到了消息

來源：程序員人生發(fā)布時間：2016-12-09 09:06:04 閱讀次數(shù)：2516次

題意

這里寫圖片描述

思路

乍1看題，冒出來的思路是，將每一個用戶凡是在同1個群的兩個用戶看作是1條無向邊，這樣所有群的所有用戶之間的聯(lián)系就轉(zhuǎn)化為了1張圖，然后以官方用戶(id=1)為出發(fā)點，計算所有可以到達(dá)的節(jié)點的總數(shù)，dfs便可，按著這個思路正準(zhǔn)備開始寫，發(fā)現(xiàn)id max為100000，2維數(shù)組是開不了了，臨界表的話未免也太繁瑣了。
才突然意想到我們只需要對所有用戶之間的連通性進(jìn)行判斷，至于具體的連通順序根本不需要肯定，那末呼之欲出了，并查集。
在并查集基礎(chǔ)之上，用每一個集的頂節(jié)點為標(biāo)識，記錄每一個集的節(jié)點總數(shù)，在集合并時對總數(shù)進(jìn)行更新，1個數(shù)組就能夠解決。

代碼

#include <iostream>
#include <cstdio>

using namespace std;

#define N 100009

int p[N];
int fa[N];
int d[1009];

int find(int x)
{
    if(fa[x] == -1)
        return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    int m;
    scanf("%d", &m);
    memset(fa, -1, sizeof(fa));
    for(int i=0; i<=100000; i++)
        p[i] = 1;
    for(int i=0; i<m; i++)
    {
        int k;
        scanf("%d", &k);
        for(int j=0; j<k; j++)
            scanf("%d", &d[j]);
        int x = find(d[0]);
        for(int j=1; j<k; j++)
        {
            int y = find(d[j]);
            if(x != y)
            {
                fa[y] = x;
                p[x] += p[y];
            }
        }
    }
    int x = find(1);
    printf("%d\n", p[x]-1);

    return 0;
}