Problem
题目大意：给你一个链表，再给你一些合法的节点，问你链表中有多少个连通分量（所有节点必须合法）。
https://leetcode.com/problems/linked-list-components/description/
We are given head, the head node of a linked list containing unique integer values.
We are also given the list G, a subset of the values in the linked list.
Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.
Example 1:
Input: head: 0->1->2->3 G = [0, 1, 3] Output: 2 Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.
Example 2:
Input: head: 0->1->2->3->4 G = [0, 3, 1, 4] Output: 2 Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.
Note:
- If
Nis the length of the linked list given byhead,1 <= N <= 10000. - The value of each node in the linked list will be in the range
[0, N - 1]. 1 <= G.length <= 10000.Gis a subset of all values in the linked list.
Solution1: Graph Traversal using DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua // Running time: 76 ms class Solution { public: int numComponents(ListNode* head, vector<int>& G) { unordered_set<int> f(G.begin(), G.end()); unordered_map<int, vector<int>> g; int u = head->val; while (head->next) { head = head->next; int v = head->val; if (f.count(v) && f.count(u)) { g[u].push_back(v); g[v].push_back(u); } u = v; } int ans = 0; unordered_set<int> visited; for (int u : G) { if (visited.count(u)) continue; ++ans; dfs(u, g, visited); } return ans; } private: void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) { if (visited.count(cur)) return; visited.insert(cur); for (const int next : g[cur]) dfs(next, g, visited); } }; |
Solution 2: Count tail node in sub graph
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua // Running time: 35 ms class Solution { public: int numComponents(ListNode* head, vector<int>& G) { unordered_set<int> g(G.begin(), G.end()); int ans = 0; while (head) { if (g.count(head->val) && (!head->next || !g.count(head->next->val))) ++ans; head = head->next; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment