Maximum matching in graph
If you don't know the size of your array, don't estimate it

Your graph is an array of 1000 std::list&lt;int&gt;. Why ? If you don't know the size, just don't use a const expr to set it. Just use any dynamic table object available (vector, hashmap, etc...).
If you have only 3 edges, 997 cells of your graph will be wasted memory space, and if you have more than 1000 edges, errors will occur.

Avoid non-const global variables

n, res and cnt are declared as global. Avoid using non-const globals. Among many problems (like name conflicts or multi-threading), it greatly reduce the readability of your program, and thus it's more easy for you to make errors.

Try declaring variables in the most restrained scope as possible. In a struct for example, which is passed down to checkPlayers. Global variable are almost never required to do what you want, you can always use local variables.
Plus, you should prefix your globals' name with g_ so it is clear that they are globals.

On top of that, you only use these variables into checkPlayers() ! These really should be local variable to this function.

Don't call list.end() in the `for` loop head

In your for loop, each time list.end() is called and re-evaluated. Just declare a const iterator with this value  like that :

std::list&lt;int&gt;::const_iterator iterator;
std::list&lt;int&gt;::const_iterator iteratorEnd = list.end();
for(iterator = list.begin(); iterator != iteratorEnd ; ++iterator){
...
}


You also should consider using std::for_each or BOOST_FOREACH (I have a preference for the latest, as it is shorter than the former to implement).

use const reference to pass non-basic types

Passing objects by copy may be long (your graph contains a 1000 cells array !), so passing it by reference is way quicker. To ensure that the reference isn't modified though, make the reference const (const Graph &amp; graph instead of Graph graph). The same goes for the std::string.

Create variables only where you need it

Besides the fact that the two arrays of bool could be move into a single array of struct containing the bools, four of the five arguments of checkPlayers are useless. Don't create them above is you don't need to, there's no use for that.

If you're doing this just in case you may need it later, well I think this is the wrong way to do it, because you may end up with tons of useless code difficult to maintain. Declare variables only when you need it, and if yo ulater may need to generalize, you'll do it then, not before.

main returns an int

Don't forget the return 0; at the end of your program. Error codes are important.