I understand that each DFS has O(N) time complexity and we call DFS for each node. That being said, we only run DFS if the node is not visited.

For example, let's say we have 6 cities indexed 0 through 5. City 0 through 3 are connected (i.e., they form a province) and city 4 and 5 are connected (i.e., they form another province). The algorithm runs DFS on city 0 but skips the DFS call for city 1, 2, and 3 since they will have already been visited. The algorithm will then make a DFS call for city 4 and skip the DFS call for city 5. Therefore, we will never call DFS for every node in the graph, it will be called enough times to visit each node once (O(n)). Am I misunderstanding?