How to solve Line Line Line Graph

[ashish99hanny]

For 30 points you can go through this link

HAMILG - Editorial

PROBLEM LINK: Practice Contest Author: Jakub Safin Tester: Mugurel Ionut Andreica Editorialist: Lalit Kundu DIFFICULTY: Hard PREREQUISITES: game theory, graphs, maximum matching, Edmonds’ blossom algorithm PROBLEM: Two players, A and B, play a game with a token on an undirected graph G. The game goes as follows: A chooses a starting vertex and places the token on this vertex. The players now alternate turns; B moves first. In his turn, each player has to move the token along exactl…

The setters solution passes it for 30 points as largest independent set in L(G) = maximum matching in G so you just output max_matching size .