Longest Consecutive Sequence in Graph


  • 0
    M
      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.


  • 0
    W

    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:

    • Find edges with consecutive nodes, e.g. 2-3, 4-5, etc.;
    • Sort those edges;
    • Find the longest consecutive edges;
    • Constraints: All nodes are distinct;

    Total time complexity is O(N*logN), where N is the number of edges.


  • 0
    T

    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,

    1. {{1,2},{2,1}}
      2: {{1,2},{2,1},{4,5},{5,4}},
      3 : {{1,3},{2,1},{4,5},{5,4},{3,1}},
      4 : {{1,5},{2,1},{4,5},{5,1},{3,1}},
    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 == max-1)
                    {
                        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;
            }
    

  • 0
    N

    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
    

  • 0
    E
    1. Use dictionary to store the mapping of each number. Such as dic[1]=3, dic[2]=3, dic[2]=4.
    2. Then generate new dictionary which only has mapping like dic[n]=n+1
    3. In the new dictionary, if the value of key is also a key, then add it to the consecutive sequence list.
    #!/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
    

  • 2
    G

    Maybe I'm missing something, so your input will be helpful. Why not do a simple DFS + memoization.

    For each unvisited node:

    • run a DFS from that Node only through nodes that create increasing sequence.
    • If one of those nodes has already been visited, just return its LIS and break.
    • Add this node with its updated LIS to the visited map

    return the maximum.


  • 0

    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(f-t) == 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
    

  • 0

    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;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.