LintCode 897. Island City - Weekly9

http://www.lintcode.com/en/problem/island-city/

You could use UnionFind, I just don't bother doing it.

As the islands are not dynamic UnionFind is unnecessary.

Just use plain old DFS, trigger it with a simple scan for cities that's not visited, then paint all visited cities with 2(or maybe not, it doesn't matter now).

Then count the number of triggers.

Boom!