instead of using $parent = get_category($cat->category_parent);
try
$category_obj = get_category($cat);
$parent = $category_obj -> category_parent;
$parent_obj = get_category($parent);
the result will be
$cat is set to the current categories id (magically)
$parent will be set to the parents id
you may or not need $parent_obj
