We present a stateless model checking algorithm for verifying concurrent programs running under RC11, a repaired version of the C/C++11 weak memory model without dependency cycles. Unlike previous approaches, which enumerate thread interleavings up to some partial order reduction improvements, our approach works directly on execution graphs and (in the absence of RMW instructions) avoids redundant exploration by construction. We have implemented a model checker, called RCMC, based on this approach and apply it to a number of challenging concurrent programs. Our experiments confirm that our tool leads to much faster verification times than other model checking tools.