## Problem description

Vertices $$\V\$$ of directed graph $$\G=(V,E)\$$ represent gossipping ladies; edge $$\(u,v) \in E\$$ signifies that lady $$\u\$$ knows of lady $$\v\$$ (which does not imply that lady $$\v\$$ knows of lady $$\u\$$). Assume that each lady knows of herself.

Intuitively, lady $$\a\$$ gossips about every lady $$\b\$$ she knows about, except herself, to every other lady $$\c\$$ whom $$\a\$$ knows about (other than $$\b\$$ herself). Lady $$\c\$$, upon hearing gossip from lady $$\a\$$ about lady $$\b\$$, will learn about $$\b\$$ but not about $$\a\$$. For $$\c\$$, this then means two things:

• $$\c\$$ will from now on gossip about $$\b\$$ to all other ladies she knows about, and
• $$\c\$$ will from now on gossip to $$\b\$$ about all other ladies she knows about, except about her own self.

Formally, the Gossip Operation $$\g(G)\$$ produces a graph $$\G' = (V, E')\$$, where $$E' = E \ \cup\ \{(c,b) \ \vert\ \exists\ (a,b) \in E : a \neq b \ \land\ \exists\ (a,c) \in E: c \neq b \}$$

The Gossip Closure of a graph $$\G\$$ is the fixed point of the Gossip Operation starting from $$\G\$$.

## Example

Input:

a:{a,b,c,d}
b:{b,e}
c:{c,d}
d:{d}
e:{e}
f:{f,a}
g:{g}


Output:

a:{a,b,c,d}
b:{b,e,c,d}
c:{c,d,b,e}
d:{d,b,c,e}
e:{e,b,c,d}
f:{f,a}
g:{g}


### Larger example

Original graph

After one iteration

Closure

Loops not shown in graphs.

Implement an algorithm of lowest possible time complexity, which given an directed unweighted graph* $$\G\$$ in any suitable format (viz. any format supporting directed unweighted graphs), outputs its Gossip Closure.
• I think the math notation in the problem statement is too much and makes it intimidating, despite the good explanation in terms of gossip. Would it not work to say that the gossip closure of a graph G is the smallest graph G' that contains all the edges of G, and that whenever (a,b) and (a,c) are edges of G', so is (b,c)? Though now having written that, it seems like all edges between pairs of a,b,c end up in the closure this way. – xnor Feb 13 at 7:02