New answers tagged dag
1
Okay I'm writing another answer for the sake of tidiness.
I suppose that the elements of your sets are integers.
Otherwise one could just use pointers to the items.
// INPUT
sets := vector of your sets
// BUILDING INVERTED INDEX
sets_of := map of int (an item) to vector of int (indices of all sets containing it)
for i, set in enumerate(sets):
for item ...
1
I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive.
From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:
...
0
Okay let's say you got $n$ matrices $M_1,M_2,...,M_n$ with dimensions $a_1\times b_1,...,a_n\times b_n$.
Now we look at what happens to the dimension when we multiply two matrices $M_i, M_j, i\neq j$:
$$(a_i\times b_i)(a_j\times b_j) = a_i \times b_j$$
Notice that you can only multiply the two matrices iff $b_i = a_j = p$:
$$(a_i\times p)(p\times b_j) = a_i \...
1
This is a comment
There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is ...
1
This is a very well-known problem, known as topological sorting.
Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.
1
For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$.
Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too.
For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call ...
Top 50 recent answers are included
