Yes. The relationship fields are stored in the database. When records are restored, the relationship fields are updated for all the child records as the parent records get new Salesforce ID’s. This is a patented process that allows one-pass restore of related data, including recursive relationships.
Contact.AccountID –> Account.ID
Contact.ReportsToID — Contact.ID
Even multi-level relationships are supported (Account1 has Contact1 as its child, which has Account2 as its child in a custom relationship).