Should I just use two different inserts starting with the parent or is there a better way?
You can temporally disable the constrains and insert all data then enable them again using the EnforceConstraints property.
myDataSet.EnforceConstraints = false;
// insert to parent and child. insert order does not matter since constraints are
// disabled
myDataSet.EnforceConstraints = true;