This paper studies the problem of majority-rule-based collective decision-making where the agents' preferences are represented by CP-nets (Conditional Preference Networks). As there are exponentially many alternatives, it is impractical to reason about the individual full rankings over the alternative space and apply majority rule directly. Most existing works either do not consider computational requirements, or depend on a strong assumption that the agents have acyclic CP-nets that are compatible with a common order on the variables. To this end, this paper proposes an efficient SAT-based approach, called MajCP (Majority-rule-based collective decision-making with CP-nets), to compute the majority winning alternatives. Our proposed approach only requires that each agent submit a CP-net; the CP-net can be cyclic, and it does not need to be any common structures among the agents' CP-nets. The experimental results presented in this paper demonstrate that the proposed approach is computationally efficient. It offers several orders of magnitude improvement in performance over a Brute-force algorithm for large numbers of variables.