Addressing non-convexity plays a fundamental role in solving the optimal electricity-gas flow models. In this paper, an improved spatial branch-and-bound algorithm is proposed to solve the non-convex problem, which is formulated as a mixed-integer bilinear programming, for its exact solution. The core of the algorithm is to divide the non-convex model into small and convex sub-problems by branching on some specific continuous variables, so that the problem can be equivalent to a rooted tree for exploration. The exactness of the algorithm is guaranteed by the same criterion as the classical branch-and-bound algorithm. To alleviate the computational burden, a novel two-stage spatial branching strategy is developed to improve the effectiveness and efficiency of the branching operations. The performance of the proposed algorithm is verified on two integrated electricity-gas systems with different sizes. Numerical results demonstrate that our method achieves a balance among feasibility, optimality and efficiency. The comparison with another 6 convexification-based methods, 3 state-of-the-art non-convex optimization solvers, and 2 spatial branch-and-bound algorithms with classical branching rules further shows the superiority of the proposed algorithm.