For a problem to be in NP, it must be solvable/decidable in nondeterministic polynomial time. This means that all the O(n^2), O(n log n), and even O(n^10) problems are in the class.
We can consider union-find to be in the class, though we'd have to be clever about formulating the sequence of actions in union find appropriately.
NP complete problems can all be polynomially reduced to each other, and indeed any NP problem can be polynomially reduced to an NP complete problem. That's why they're called NP complete. But there are plenty of problems in NP to which other NP problems cannot be polynomially reduced. |