1
\
2  3
\ /
4

5  8
 /
7
For the undirected graph, the LCS is 2,3,4,5, so how can we find it?
The input may be List<int[]> edges.
Code:
class Solution {
public:
// NOTE: Nodes are distinct
vector<int> LCS(const vector<pair<int, int>> & edges) {
vector<int> t;
for (auto e : edges) {
if (e.first > e.second)
swap(e.first, e.second);
if (e.first + 1 == e.second)
t.push_back(e.first);
}
if (t.empty())
return{};
sort(t.begin(), t.end());
size_t c = 0, cl = 1, r = c, rl = cl;
for (size_t i = 1; i < t.size(); ++i)
if (t[i  1] + 1 == t[i]) {
cl = i  c + 1;
if (cl > rl)
r = c, rl = cl;
} else
c = i, cl = 0;
vector<int> ret(t.begin() + r, t.begin() + r + rl);
ret.push_back(ret.back() + 1);
return ret;
}
};
Explanation:
Total time complexity is O(N*logN), where N is the number of edges.
My idea is to find the boundary for consecutive,
in mapping i will set min's max boundary, and max's min boundary,
eg.
{
{1,2},
{4,5}
{2,3}
{4,3}
}
for mapping,
static List<int> fun(int[,] input) {
List<int> result = new List<int>();
Dictionary<int, int> mapping = new Dictionary<int, int>();
int rows = input.GetLength(0);
int resultIndex = 0;
int r = 0;
for (int i = 0; i < rows; i++) {
int min = Math.Min(input[i,0], input[i, 1]);
int max = Math.Max(input[i, 0], input[i, 1]);
if (!mapping.ContainsKey(min))
{
mapping.Add(min, min);
}
if (!mapping.ContainsKey(max))
{
mapping.Add(max, max);
}
if (min == max1)
{
int t_min = Math.Min(mapping[min], mapping[max]);
int t_max = Math.Max(mapping[min], mapping[max]);
mapping[t_min] = t_max;
mapping[t_max] = t_min;
if (t_max  t_min > r) {
r = t_max  t_min;
resultIndex = t_min;
}
}
}
if (r == 0)
{
return result;
}
for (int i = resultIndex; i <= mapping[resultIndex]; i++) {
result.Add(i);
}
return result;
}
If you use a heap, then you can solve this with E+VlogV time complexity. E for processing the initial edges, VlogV for heapifying and then iterating through the vertices.
from collections import defaultdict
def get_longest_consecutive_sequence(edges):
g = defaultdict(set)
vertices = set()
for e in edges:
vertices.add(e[0])
vertices.add(e[1])
g[e[0]].add(e[1])
g[e[1]].add(e[0])
heap = list(vertices)
heapq.heapify(heap)
last = heapq.heappop(heap)
sequence_so_far = [last]
max_sequence = [last]
while heap:
curr = heapq.heappop(heap)
if curr  1 == last and last in g[curr]:
sequence_so_far.append(curr)
if len(sequence_so_far) > len(max_sequence):
max_so_far = sequence_so_far
max_sequence = sequence_so_far
else:
sequence_so_far = [curr]
last = curr
return max_sequence
# 1
# \
# 2  3
# \ /
# 4
# 
# 5  8
#  /
# 7
assert len(get_longest_consecutive_sequence([[1,3],[2,3],[4,5],[5,7],[3,4],[7,8],[2,4],[5,8]])) == 4
#!/usr/bin/python
def getConsecutiveSequence(dic):
# Get the consecutive dictionary which mapping like dic[n]=n+1
conDic = {}
for key in dic:
if (dic[key] == key + 1):
conDic[key] = dic[key]
# Sort the consecutive dictionary by keys
sortedKeys = sorted(conDic.keys())
# Check each key in consecutive dictionary, if its value is also key in consecutive dictionary, then add that value in the consecutive sequence list
conlist = [sortedKeys[0]]
lastKey = sortedKeys[0]
for key in sortedKeys:
if conDic[key] in conDic.keys():
conlist.append(conDic[key])
lastKey = conDic[key]
conlist.append(conDic[lastKey])
return conlist
dic = {}
dic[1] = 3
dic[2] = 3
dic[3] = 4
dic[4] = 5
dic[5] = 8
dic[5] = 7
dic[8] = 7
conlist = getConsecutiveSequence(dic)
print conlist
Maybe I'm missing something, so your input will be helpful. Why not do a simple DFS + memoization.
For each unvisited node:
return the maximum.
Correct me if I'm wrong, but I think it's safe to assume that there won't be any duplicate vertices (numbers) as we can't generate a unique graph out of an edge list if there are duplicates. With this assumption, we can generate a new directed graph from the original edge list by processing each edge and adding an edge to our new graph iff the difference in value between the two vertices are equal to 1. After doing so we just need to perform a DFS from each node to find the longest path rooted at each node. Since we'd be dealing with a directed graph in our modified problem, we can perform a top sort to perform DFS in topological order to ensure we find the maximum path rooted at each node. Space complexity will be O(V) as we're just storing all vertices, and time complexity will be O(V + E) since we're processing each edge once then processing each vertex a constant number of times.
from collections import defaultdict, deque
def dfs(v, G, V):
if v in V: return 0
V.add(v)
cnt = 1
for vt in G.get(v,[]):
cnt += dfs(vt, G, V)
return cnt
def top_sort(v, G, V, order):
if v in V: return
V.add(v)
for vt in G.get(v, []):
top_sort(vt, G, V, order)
order.appendleft(v)
def longest_consecutive(edges):
if not edges: return 0
G = defaultdict(list)
for f,t in edges:
if abs(ft) == 1:
if f > t:
G[t].append(f)
else:
G[f].append(t)
order = deque()
V = set()
for v in G:
top_sort(v, G, V, order)
mx = 1
V = set()
while order:
mx = max(mx, dfs(order.popleft(), G, V))
return mx
My O(V + E) solution in CPP is:
typedef vector<vector<int> > Graph;
list<int> consecutive_path(const Graph & g, int i) {
list<int> res;
while (i < g.size()) {
res.push_back(i);
if (find(g[i].begin(), g[i].end(), i + 1) != g[i].end())
i++;
else
break;
}
return res;
}
list<int> solve(const Graph & g) {
list<int> res;
list<int> path;
path.push_front(g.size()  1);
for (int i = g.size()  2; i > 0; i) { //vertices are numbered from 1.
if (find(g[i].begin(), g[i].end(), i + 1) != g[i].end()) {
path.push_front(i);
}
else {
path = consecutive_path(g, i);
}
if (path.size() > res.size()) {
res = path;
}
}
return res;
}