[leetcode] 並查集（Ⅱ）_包裝設計

※產品缺大量曝光嗎?你需要的是一流包裝設計!

窩窩觸角包含自媒體、自有平台及其他國家營銷業務等，多角化經營並具有國際觀的永續理念。

最長連續序列

題目[128]：鏈接。

解題思路

節點本身的值作為節點的標號，兩節點相鄰，即允許合併(x, y)的條件為x == y+1 。

因為數組中可能會出現值為 -1 的節點，因此不能把 root[x] == -1 作為根節點的特徵，所以採取 root[x] == x 作為判斷是否為根節點的條件。默認較小的節點作為連通分量的根。

此外，使用 map<int, int> counter 記錄節點所在連通分量的節點個數（也是merge 的返回值）。

class Solution
{
public:
    unordered_map<int, int> counter;
    unordered_map<int, int> root;
    int longestConsecutive(vector<int> &nums)
    {
        int len = nums.size();
        // use map to discard the duplicate values
        for (int x : nums)
            root[x] = x, counter[x] = 1;
        int result = len == 0 ? 0 : 1;
        for (int x : nums)
        {
            if (root.count(x + 1) == 1)
                result = max(result, merge(x, x + 1));
        }
        return result;
    }
    int find(int x)
    {
        return root[x] == x ? x : (root[x] = find(root[x]));
    }
    int merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x != y)
        {
            root[y] = x;
            counter[x] += counter[y];
        }
        return counter[x];
    }
};

連通網絡的操作次數

題目[1319]：Link.

解題思路

考慮使用並查集。

考慮到特殊情況，要使 N 個點連通，至少需要 N-1 條邊，否則返回 -1 即可。

通過並查集，可以計算出多餘的邊的數目（多餘的邊是指使得圖成環的邊），只要 findroot(x) == findroot(y) 說明邊 (x,y) 使得圖成環。

遍歷所有邊，在並查集中執行合併 merge 操作（多餘的邊忽略不合併，只進行計數）。設 components 為合併后后 root 數組中 -1 的個數（也就是連通分量的個數），要想所有的連通分支都連起來，需要 components - 1 個邊，所以要求「多餘的邊」的數目必須大於等於 components - 1。

一個簡單的例子如下：

0--1         0--1                0--1
| /    =>    |          =>       |  | 
2  3         2  3                2  3
             components = 2
             duplicateEdge = 1

代碼實現

class Solution
{
public:
    vector<int> root;
    int result = 0;
    int makeConnected(int n, vector<vector<int>> &connections)
    {
        int E = connections.size();
        // corner cases
        if (n == 0 || n == 1)
            return 0;
        if (E < n - 1)
            return -1;
        root.resize(n), root.assign(n, -1);
        // merge
        for (auto &v : connections)
        {
            int a = v[0], b = v[1];
            merge(a, b);
        }
        int components = count(root.begin(), root.end(), -1);
        if (counter >= (components - 1))
            return components - 1;
        // should not be here
        return -1;
    }
    int find(int x)
    {
        return root[x] == -1 ? x : (root[x] = find(root[x]));
    }
    // the number of duplicate edges
    int counter = 0;
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            root[y] = x;
        else
        {
            // there is a duplicate edge
            counter++;
        }
    }
};

等式方程的可滿足性

題目[990]：Link.

解題思路

考慮並查集。遍歷所有的包含 == 的等式，顯然，相等的 2 個變量就合併。對於不等式 x!=y ，必須滿足 findroot(x) != findroot(y) 才不會出現邏輯上的錯誤。也就是說，不相等的 2 個變量必然在不同的連通分支當中。

#define getidx(x) ((x) - 'a')
class Solution
{
public:
    vector<int> root;
    bool equationsPossible(vector<string> &equations)
    {
        root.resize('z' - 'a' + 1, -1);
        vector<int> notequal;
        int len = equations.size();
        for (int i = 0; i < len; i++)
        {
            auto &s = equations[i];
            if (s[1] == '!')
            {
                notequal.emplace_back(i);
                continue;
            }
            int a = getidx(s[0]), b = getidx(s[3]);
            merge(a, b);
        }
        for (int i : notequal)
        {
            auto &s = equations[i];
            int a = getidx(s[0]), b = getidx(s[3]);
            if (find(a) == find(b))
                return false;
        }
        return true;
    }
    int find(int x)
    {
        return (root[x] == -1) ? x : (root[x] = find(root[x]));
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            root[y] = x;
    }
};

盡量減少惡意軟件的傳播 II

題目[928]：這題有點難。

解題思路

參考 題解1 和 題解2 。

※南投搬家公司費用需注意的眉眉角角，別等搬了再說!

上新台中搬家公司提供您一套專業有效率且人性化的辦公室搬遷、公司行號搬家及工廠遷廠的搬家服務

首先，對原來的並查集結構添加一點改進，利用 vector<int> size[N] 記錄某個連通分量中節點的數目，注意當且僅當 x 是該連通分量的根節點時，size[x] 才表示該連通分量的節點數目。這是因為在 merge 中，只對根節點的 size 進行了處理。

vector<int> root;
vector<int> size;
int find(int x)
{
    return root[x] == -1 ? (x) : (root[x] = find(root[x]));
}
void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x != y)
        root[y] = x, size[x] += size[y];	// pay attention here
}
// get the size of the connected component where node x is in
int getComponentSize(int x)
{
    return size[find(x)];
}

然後，建立一個基本圖，該圖是原圖 graph 去除所有感染節點 initial 的結果，並把這個基本圖轉換為上述改進后的並查集。把這個基本圖中的節點暫且稱為 clean nodes 或者 non-infected nodes .

從直覺上來說，我們應該在 initial 中找到那個標號最小，感染最多 non-infected nodes 的節點，但是這樣是否符合預期？

顯然是不符合的，來看個例子，設 initial nodes = [a,b,c] ，並設 2 個沒有被感染的連通分量為 N1, N2 ，且這 2 個連通分量的點數滿足 size(N1) > size(N2)，原圖 graph 結構如下：

a--N1--c

b--N2

根據題目的意思，需要找到的是使得最終感染數目 M(initial) 最小的節點。

如果我們按照上述所謂的「直覺」：“在 initial 中找到那個感染最多 non-infected nodes 的節點”，應該去除的是節點 a ，但是由於 c 的存在，N1 依舊會被感染，這樣 M(initial) = size(N1) + size(N2)。（也就是說，某個連通分量相鄰的感染節點多於 1 個，該連通分量最終是必然被感染的，因為我們只能去除一個感染節點。）

實際上，這種情況下正確答案是去除 b ，因為除 b 后：M(initial) = size(N1) ，該結果才是最小的。

所以，我們要找的是：在 initial 中找到那個感染最多 non-infected nodes 的節點 ans，但這些 non-infected nodes 節點只能被 ans 感染，不能被其他的 initial 節點感染（即只能被感染一次）。

代碼實現

class Solution
{
public:
    vector<int> root;
    vector<int> size;
    int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial)
    {
        int N = graph.size();
        root.resize(N, -1);
        size.resize(N, 1);

        // use hash table to mark infected nodes
        vector<bool> init(N, false);
        for (int x : initial)
            init[x] = true;
        // change the non-infected graph into disjoint union set
        for (int i = 0; i < N; i++)
        {
            if (init[i])
                continue;
            for (int j = 0; j < i; j++)
            {
                if (init[j])
                    continue;
                if (graph[i][j] == 1)
                    merge(i, j);
            }
        }
        // table[x] = {...}
        // the set {...} means the non-infected components which initial node x will infect
        // counter[x] = k
        // k means that the non-infected component x will be infected by initial nodes for k times
        vector<int> counter(N, 0);
        unordered_map<int, unordered_set<int>> table;
        for (int u : initial)
        {
            unordered_set<int> infected;
            for (int v = 0; v < graph[u].size(); v++)
            {
                if (!init[v] && graph[u][v] == 1)
                    infected.insert(find(v));
            }
            table[u] = infected;
            for (int x : infected)
                counter[x]++;
        }

        // find the node we want
        int ans = N + 1, maxInfected = -1;
        for (int u : initial)
        {
            int sum = 0;
            for (int x : table[u])
                if (counter[x] == 1)	// must be infected only once
                    sum += getComponentSize(x);
            if (sum > maxInfected || (sum == maxInfected && u < ans))
            {
                ans = u;
                maxInfected = sum;
            }
        }
        return ans;
    }

    int find(int x)
    {
        return root[x] == -1 ? (x) : (root[x] = find(root[x]));
    }

    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            root[y] = x, size[x] += size[y];
    }

    int getComponentSize(int x)
    {
        return size[find(x)];
    }
};

盡量減少惡意軟件的傳播

題目[924]：做了上面那題之後簡單一點。

解題思路

依然是使用上題中 盡量減少惡意軟件的傳播 II 改進后的並查集結構。

對整個原圖處理，轉換為並查集。然後，模擬處理。即 \(\forall x \in initial\) ，使用集合 \(newSet = initial – \{x\}\) 去模擬感染原圖，得到最終的感染節點數 t，選取感染節點數 t 最小且標號值最小的 \(x\) 作為返回結果。

代碼實現

class Solution
{
public:
    vector<int> root, size;
    int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial)
    {
        int N = graph.size();
        root.resize(N, -1);
        size.resize(N, 1);

        for (int i = 0; i < N; i++)
            for (int j = 0; j < i; j++)
                if (graph[i][j] == 1)
                    merge(i, j);

        int ans = N + 1, minval = N + 1;
        // assume that discard the node x in the initial set
        // get the injected value
        for (int x : initial)
        {
            int t = getInjected(x, initial);
            if (t < minval || (t == minval && ans > x))
            {
                minval = t;
                ans = x;
            }
        }
        return ans;
    }
    // use set initial - {x} to inject the graph
    int getInjected(int x, vector<int> &initial)
    {
        unordered_set<int> s;
        for (int k : initial)
        {
            if (k == x)
                continue;
            s.insert(find(k));
        }
        int sum = 0;
        for (int t : s)
            sum += size[find(t)];
        return sum;
    }
    int find(int x)
    {
        return root[x] == -1 ? (x) : (root[x] = find(root[x]));
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            root[y] = x, size[x] += size[y];
    }
};

被圍繞的區域

題目[130]：本題難度一般。

解題思路

本題最特殊的節點是邊界上的 O 以及內部與邊界 O 相鄰的節點。

首先，通過邊界的 O 入手，從它開始進行 DFS 搜索，把所有這些的特殊節點標記為 Y 。然後，在 board 中剩下的 O 就是普通的節點（必然是不與邊界 O 相鄰且被 X 所圍繞的），可以把它們全部換成 X 。最後，把所有的 Y 還原為 O 。

對於搜索方法，既可以是 DFS 也可以是 BFS。

代碼實現

class Solution
{
public:
    const vector<vector<int>> direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int row, col;
    void solve(vector<vector<char>> &board)
    {
        row = board.size();
        if (row == 0)
            return;
        col = board[0].size();
        #define func bfs
        for (int j = 0; j < col; j++)
        {
            if (board[0][j] == 'O')
                func(0, j, board);
            if (board[row - 1][j] == 'O')
                func(row - 1, j, board);
        }

        for (int i = 0; i < row; i++)
        {
            if (board[i][0] == 'O')
                func(i, 0, board);
            if (board[i][col - 1] == 'O')
                func(i, col - 1, board);
        }

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == 'Y')
                    board[i][j] = 'O';
            }
        }
    }

    void dfs(int i, int j, vector<vector<char>> &board)
    {
        board[i][j] = 'Y';
        for (auto &v : direction)
        {
            int a = i + v[0], b = j + v[1];
            if (a < 0 || b < 0 || a >= row || b >= col)
                continue;
            if (board[a][b] == 'O')
                dfs(a, b, board);
        }
    }

    void bfs(int i, int j, vector<vector<char>> &board)
    {
        typedef pair<int, int> node;
        queue<node> q;
        q.push(node(i, j));
        board[i][j] = 'Y';
        while (!q.empty())
        {
            node n = q.front();
            q.pop();
            for (auto &v : direction)
            {
                int a = n.first + v[0], b = n.second + v[1];
                if (!(a < 0 || b < 0 || a >= row || b >= col) && board[a][b] == 'O')
                    board[a][b] = 'Y', q.push(node(a, b));
            }
        }
    }
};

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網動廣告出品的網頁設計，採用精簡與質感的CSS語法，提升企業的專業形象與簡約舒適的瀏覽體驗，讓瀏覽者第一眼就愛上她。