How to find the number of loose parts with Blender's Python API?
Recursive Bmesh version

Similarly to the way  other bmesh operators, BMesh.Ops are used, 

get_islands(bm, verts=[])

bm the bmesh. 
verts  iterarable of any or all of the verts in the bmesh. 
 returns -> dict(islands=[]) 

A dictionary is returned with each island as a list of BMVerts, within  the "islands" key list.


It's Quick 
Uses BMVert.tag so doesn't naff up prior selections.
Works in both edit and object mode
Requires no operators.


.
Test code: Run in object mode, checks for all islands in all meshes in file. 

import bpy
import bmesh

def walk_island(vert):
    ''' walk all un-tagged linked verts '''    
    vert.tag = True
    yield(vert)
    linked_verts = [e.other_vert(vert) for e in vert.link_edges
            if not e.other_vert(vert).tag]

    for v in linked_verts:
        if v.tag:
            continue
        yield from walk_island(v)

def get_islands(bm, verts=[]):
    def tag(verts, switch):
        for v in verts:
            v.tag = switch
    tag(bm.verts, True)
    tag(verts, False)
    ret = {"islands" : []}
    verts = set(verts)
    while verts:
        v = verts.pop()
        verts.add(v)
        island = set(walk_island(v))
        ret["islands"].append(list(island))
        tag(island, False) # remove tag = True
        verts -= island
    return ret

#test code
context = bpy.context
ob = context.object
me = ob.data
bm = bmesh.new()
from time import time
t = time()
for me in bpy.data.meshes:
    bm.from_mesh(me)
    islands = [island for island in get_islands(bm, verts=bm.verts)["islands"]]
    print(me.name, "Islands:", len(islands))
    print([len(i) for i in islands])
    bm.clear()

bm.free()
print(len(bpy.data.meshes), "meshes processed in", time() - t, "seconds")


Given the new answers, thought I'd time them.  Simple 10 x 10 x 10 applied array on default cube.

This

Cube Islands: 1000
0.0809781551361084 seconds


@Денис Колесников

1000
0.11966490745544434


@lemon

islands 1000
0.18735790252685547


@zebus_3d  (note leaves the object in edit mode)

# by faces
total islands:  1000
total time (seconds):  6.521913093005423
# by verts
total islands:  1000
total time (seconds):  10.745814517998951


JakeD

1000
18.090813398361206  seconds