I have a solution that I cannot prove whether it is true or not. However it passed all the final tests. See my code here 4635501
- Pick up 1 unmarked vertice w and 2 marked vertices u & v. The rest vertices are in the set V0.
- Add edge between vertices {w + v + V0} to form a complete undirected graph.
- Add edge between vertices w & u.
- Add edge between vertices u & all vertices in set S which are unmarked.
The maximum number of edges is (n-1)*(n-2)/2+1+(n-k-1).
I thinks some details:
First , this graph is connected.
Second , if (n==k) it is right(Should output -1)
Third , It's unnecessary to get two marked verices. I think only one is enough. This one is connected with none of the marked vertices. Beacause of k>=2 We can find it is not connected with other marked vertices.
My solotion ID is 4631948