Finding the maximum common induced subgraph between two graphs is a fundamental problem with diverse applications, ranging from chemistry to social network analysis. The McSplit algorithm, which is based on a partitioning-based branch-and-bound approach, has demonstrated remarkable efficiency in solving this problem by leveraging an upper bound to prune unproductive search paths. However, existing improvements to the McSplit algorithm focus primarily on upper bound refinements, neglecting the potential of strong lower bounds for early-stage pruning. In this work, we propose a two-stage framework that bridges exploratory heuristics with exact search to address this limitation. The first stage employs a fast heuristic to identify a strong initial lower bound, while the second stage uses this bound to guide an exact backtracking search, significantly improving pruning efficiency. Our dynamic transition mechanism between the stages ensures an effective balance between exploration and exhaustive search. Extensive experimental results demonstrate that the proposed method significantly enhances McSplit and its reinforcement learning-based extensions, achieving faster computation times and better solutions across various benchmarks.