這題會給你一個undirected graph，而且是沒有cycle的
要找出多餘的連線，比如說：
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3
[1,2]就是表示1和2之間有連線，[1,3]就是表示1和3有連線，以此類推
另外裡面的數值就只會有1~N，不會重複
再舉個例子吧：
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
大概是這樣
Sol：
這題我先說，我一開始完全沒概念
真的完全不知道怎麼辦
大概只覺得可以一個一個建graph出來，然後邊建邊找這樣
不過我不太會熟graph...，但這題也可以這麼做就是
關於graph的題目，之後再來解幾題看看吧
這題主要用的概念是要用Union set
簡單說就是集合的概念
把每連結在一起的node當成一個集合，大概的意思是怎樣呢？
簡單說可以列一個大小為N的陣列來記錄每個node屬於哪個集合
在初始化的時候，每個node都屬於各自的集合：
int parent[N+1]; // 這邊只是為了方便，因為沒有0這個node
for (int i = 0; i <= N; ++i)
parent[i] = i;
接下來先看一下怎麼推吧，就拿第一個例子來說好了
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3
初始化的parent為[0,1,2,3]
第一組為[1,2]，表示1和2為同一個集合，所以把2的集合改為1，表示他們都是屬於1的這個集合
parent就會變成[0,1,1,3]
第二組為[1,3]，表示1和3為同一個集合，所以把3的集合改為1，表示他們都是屬於1的這個集合
parent就會變成[0,1,1,1]
最後一組為[2,3]，這邊一檢查就會發現他們都是屬於1的這個集合，所以[2,3]就是多餘的
大概是這個概念，只是光看這個例子會有陷阱
因為上面的例子裏沒有"要把兩個集合連在一起的情況"
比如說1,2是一個集合，3,4是一個集合，parent是[0,1,1,3,3...]
如果出現一個[1,3]的連結，那就要把1和3兩個集合連在一起
這時候怎麼做呢？
如果要把3和4都標成1的話也可以，不過其實可以把3的集合標為1就好了
只要改掉最源頭的那個node的標記就可以了，寫一個find()的函式來尋找node集合的源頭就行了：
int find(int i, const vector<int>& parent)
{
if (parent[i] == i)
{
return i;
}
else
{
return find(parent[i], parent);
}
return 0;
}
所以我們可以靠這個find()來找到node是屬於哪個集合
好吧，其實重點就是上面這個函式
有了這個東西，這題其實就解完了，大概長這樣：
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
vector<int> parent;
for(int i = 0; i <= edges.size(); ++i) // 初始化，這邊是用vector
{
parent.push_back(i);
}
for (vector<int> vi : edges) // vi表示node0和node1之間的連結
{
if (find(vi[0], parent) == find(vi[1], parent)) // 如果兩個node的集合是同一個的話，表示那是不必要的連結
{
return vi;
}
else
{
parent[find(vi[1], parent)] = find(vi[0], parent); // 把node1的集合標成node0的集合，其實倒過來也行
}
}
return vector<int>{0, 0};
}
這就是比較快速的方法，接下來看一下用graph的方法好了
graph的方法稍微不適合這題，但就當作練習吧XD
相對於上一個方法存每個node的集合，這邊會存每個node連結到哪個node：
unordered_map<int, vector<int>> adjList;
簡單說如果1和2,3,4相連，adjList[1]的內容就會是[2,3,4]
透過這個adjList，我們可以查詢是否有多餘的連結
再來就是怎麼去搜尋graph了，必須要有一個陣列之類的結構來記錄那些節點是否被走過
我們稱它為color吧：
unordered_set<int> color;
所以code大概可以長成這樣：
bool hasPath(unordered_map<int, vector<int>>& adjList,
const vector<int>& edge,
unordered_set<int>& color)
{
int from = edge[0]; // 起點和終點
int to = edge[1];
if (from == to) // 表示兩個是一樣的點，當然就是相通的
return true;
color.insert(from); // 在color裡加入from，表示這個點走過了
for (const int& adj : adjList[from]) // 去找從from開始的連結
{
if (color.count(adj) == 0) // 如果這個連結還沒被找過
{
if (hasPath(adjList, vector<int>{adj, to}, color)) // 就從這個連結繼續往to找，這邊用遞迴就可以很方便的一直找下去了
return true;
}
}
return false;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> adjList;
for (vector<int> edge : edges) // 找每個edge
{
unordered_set<int> color; // 初始化color
if (hasPath(adjList, edge, color)) // 如果edge裡的兩個node是連在一起的，表示他就是多餘的
{
return edge;
}
adjList[edge[0]].push_back(edge[1]); // 把edge裡的連結加到adjList中
adjList[edge[1]].push_back(edge[0]);
}
return vector<int>{0, 0};
}
好吧，其實解釋完之後好像也不難懂吧
只是要靠自己想出來... 就要有點實力了
不過一開始總是要先參考別人的嘛，我又不是天才對吧XD
那這題就這樣了~下題再見~
留言列表
