Sample Code

//Parent Account
Account acc = new Account();
acc.Name = 'Salesforce';
acc.ExternalID__c = '12333';//External Id

//Child Contact
Contact con = new Contact();
con.FirstName = 'John';
con.LastName = 'Doe';
con.Account = new Account(ExternalID__c = '12333');

List<Database.SaveResult> results = Database.Insert(new SObject[] {acc, con});

for (Integer i = 0; i < results.size(); i++) {
    if (results[i].isSuccess()) {
        System.debug('Successfully Created record ID: '+ results[i].getId());
    } 
}