Skip to content

Instantly share code, notes, and snippets.

  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jianminchen/254e885f720990136b872e73fbedfe08 to your computer and use it in GitHub Desktop.
maximum disjoint subtree - study code - max min tree - need to understand the time complexity
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
public class Graph
{
private Dictionary<long, Node> nodes;
private Dictionary<long, Edge> edges;
// Key = edge number with sign + or -
private Dictionary<long, long> maxTree;
private Dictionary<long, long> minTree;
private Dictionary<long, long> maxTreeInclusive;
private Dictionary<long, long> minTreeInclusive;
public Graph()
{
nodes = new Dictionary<long, Node>();
edges = new Dictionary<long, Edge>();
maxTree = new Dictionary<long, long>();
minTree = new Dictionary<long, long>();
maxTreeInclusive = new Dictionary<long, long>();
minTreeInclusive = new Dictionary<long, long>();
}
/// <summary>
/// Node class - ID, ConnectedEdges, weight, using LinkedList for ConnectedEdges
/// kind of smart using LinkedList for ConnectedEdges
/// How to define connected edges for each node?
/// Go over the sample test case to figure out, node 1 - weight -9, connected edges
/// is a linked list with 2 nodes, where first node is edge 1 which are connected by ID 1 to ID 6,
/// and the second node is edge 5 which are connected by ID 2 to ID 2.
/// </summary>
public class Node
{
public long Id { get; private set; }
public long Weight { get; private set; }
public LinkedList<Edge> ConnectedEdges;
public Node(long id, long weight)
{
Id = id;
Weight = weight;
ConnectedEdges = new LinkedList<Edge>();
}
}
public class Edge
{
public long ID { get; private set; }
public long Node1 { get; private set; }
public long Node2 { get; private set; }
public Edge(long id, long node1, long node2)
{
ID = id;
Node1 = node1;
Node2 = node2;
}
}
public void AddEdge(long edgeID, long id1, long id2)
{
var edge = new Edge(edgeID, id1, id2);
edges.Add(edgeID, edge);
var node1 = nodes[id1];
var node2 = nodes[id2];
node1.ConnectedEdges.AddLast(edge);
node2.ConnectedEdges.AddLast(edge);
}
public void AddNode(long id, long weight)
{
nodes.Add(id, new Node(id, weight));
}
private void fillMinMaxTrees()
{
foreach (var edge in edges.Values)
{
if (!maxTree.ContainsKey(edge.ID))
{
fillMinMaxTreeForEdge(edge.ID);
}
if (!maxTree.ContainsKey(-edge.ID))
{
fillMinMaxTreeForEdge(-edge.ID);
}
}
}
/// <summary>
/// how to understand the max tree for the edge?
/// Take the sample test case, and understand it.
/// It is a DFS search, for each edge, try to find max/ min value.
/// First edge with edgeID = 1, ID 6 - ID 1, so node 6 only has one extra connected edge to
/// node 3, which only has one connected edge.
/// Node Id = 1, which has connected edge 5(1-2), then DFS search to edge 4(5-2), then DFS
/// search edge 2 (4-5), node 4 has only one connected edge, easy to compute weight.
/// </summary>
/// <param name="edgeIDWithSign"></param>
private void fillMinMaxTreeForEdge(long edgeIDWithSign)
{
long edgeID = Math.Abs(edgeIDWithSign);
Edge edge = edges[edgeID];
long nodeID = edgeIDWithSign > 0 ? Math.Max(edge.Node1, edge.Node2) : Math.Min(edge.Node1, edge.Node2);
Node node = nodes[nodeID];
if (node.ConnectedEdges.Count == 1)
{
maxTree.Add(edgeIDWithSign, node.Weight);
minTree.Add(edgeIDWithSign, node.Weight);
maxTreeInclusive.Add(edgeIDWithSign, node.Weight);
minTreeInclusive.Add(edgeIDWithSign, node.Weight);
return;
}
long max = long.MinValue;
long maxInclusive = node.Weight;
long min = long.MaxValue;
long minInclusive = node.Weight;
foreach (var connectedEdge in node.ConnectedEdges)
{
if (connectedEdge.ID != edgeID)
{
long connectedNodeID = connectedEdge.Node1 == nodeID ? connectedEdge.Node2 : connectedEdge.Node1;
long connectedEdgeIDWithSign = connectedNodeID > nodeID ? connectedEdge.ID : -connectedEdge.ID;
if (!maxTree.ContainsKey(connectedEdgeIDWithSign))
{
fillMinMaxTreeForEdge(connectedEdgeIDWithSign);
}
max = Math.Max(maxTree[connectedEdgeIDWithSign], max);
min = Math.Min(minTree[connectedEdgeIDWithSign], min);
maxInclusive = Math.Max(maxTreeInclusive[connectedEdgeIDWithSign] + maxInclusive, maxInclusive);
minInclusive = Math.Min(minTreeInclusive[connectedEdgeIDWithSign] + minInclusive, minInclusive);
}
}
max = Math.Max(max, maxInclusive);
min = Math.Min(min, minInclusive);
maxTree.Add(edgeIDWithSign, max);
minTree.Add(edgeIDWithSign, min);
maxTreeInclusive.Add(edgeIDWithSign, maxInclusive);
minTreeInclusive.Add(edgeIDWithSign, minInclusive);
}
public long FindMaxProduct()
{
fillMinMaxTrees();
long maxProduct = long.MinValue;
foreach (var edge in edges.Values)
{
maxProduct = Math.Max(maxTree[edge.ID] * maxTree[-edge.ID], maxProduct);
maxProduct = Math.Max(minTree[edge.ID] * minTree[-edge.ID], maxProduct);
}
return maxProduct;
}
}
static void Main(String[] args)
{
//ProcessInput();
RunTestcase();
}
public static void RunTestcase()
{
int n = 6;
int[] weights = new int[] { -9, -6, -1, 9, -2, 0 };
int[][] edgeInfo = new int[5][];
edgeInfo[0] = new int[] { 6, 1 };
edgeInfo[1] = new int[] { 4, 5 };
edgeInfo[2] = new int[] { 6, 3 };
edgeInfo[3] = new int[] { 5, 2 };
edgeInfo[4] = new int[] { 1, 2 };
Graph graph = new Graph();
for (long i = 0; i < n; i++)
{
graph.AddNode(i + 1, weights[i]);
}
for (int i = 0; i < n - 1; i++)
{
graph.AddEdge(i+1, edgeInfo[i][0], edgeInfo[i][1] );
}
Console.WriteLine(graph.FindMaxProduct());
}
public static void ProcessInput()
{
long n = Convert.ToInt32(Console.ReadLine());
// The respective weights of each node:
string[] w_temp = Console.ReadLine().Split(' ');
int[] w = Array.ConvertAll(w_temp, Int32.Parse);
Graph graph = new Graph();
for (long i = 0; i < n; i++)
{
graph.AddNode(i + 1, w[i]);
}
for (long i = 0; i < n - 1; i++)
{
// Node IDs 'u' and 'v' are connected by an edge:
string[] tokens_n = Console.ReadLine().Split(' ');
long u = Convert.ToInt32(tokens_n[0]);
long v = Convert.ToInt32(tokens_n[1]);
graph.AddEdge(i + 1, u, v);
}
Console.WriteLine(graph.FindMaxProduct());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment