There is a graph with n vertexes and m edges. Two players are playing a game on this graph.The first player colors a vertex and the second player can color only one of the neighbors of the vertex which was colored first.After that, the first player can color one of the neighbors of the vertex which was chosen by the second one, and so on.Formaly, a player can only color a neighbor to the vertex colored last by the other player. The player who can't color a vertex anymore wins. The question is that if the first player has a strategy to win. I've solved this problem if the graph is a tree using a DP but I can't see any connections between the tree problem and this one Thank you in advance!

Does the graph consist of one connected component? If so, one can just count the number of nodes of which are not leaves I guess. But if the graph consists of multiple connected components, then DSU will divide the graph into subproblems mentioned above. Correct me if I am wrong please

Yes, the graph consist only of one component, but I don't think that has anything to do woth the number of nodes that are not leaves. Can you be a bit more precise so I can understand you?

so the way I see it is like this: players take turns selecting a node that is a neighbor of the former node selected. what the players want is to pick a vertex of which all its neighbors are selected. for this to happen, the node has to be a leaf node or a root node. Cycles really dont matter because when the cycle is fully traversed, the players can always find an option to flee the cycle regarding its parity. So in a nutshell, players are trying to fore the other to give them a chance to color the leaf nodes OR the root node. I hope I explained clearly

Can one of the players colour a vertex that was coloured before?

No, a vertex that has been colored before can't be colored again. Thank you!

In that case I know a solution at least for bipartite graphs.

https://cs.stackexchange.com/questions/17974/bipartite-graph-game

I haven't thought about how to solve it for non-bipartite graphs.

Thank you a lot!

This problem is called the "generalized geography" problem, for various reasons:

https://en.wikipedia.org/wiki/Generalized_geography#cite_note-3

The problem is intractable (PSPACE-hard) on directed graphs, and apparently it's tractable on undirected (even non-bipartite) graphs.