#Ruby, 78 bytes

Finally some use for ruby's set operators ([1,2]&[2]==[2] and [3,4,5]-[4]==[3,5]).

->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k} 

ideone, including all test cases, which it passes.

Ruby, 78 bytes

Finally some use for ruby's set operators ([1,2]&[2]==[2] and [3,4,5]-[4]==[3,5]).

->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k} 

ideone, including all test cases, which it passes.