Тут конечно можно хранить все в матрице смежности, но это вовсе не надо. Тут у нас дан граф неориентированный, т.е. если из i в j есть дорога то и из j в i она тоже есть. Значит если мы посчитаем кол-во единиц в матрице, то это будет удвоенный ответ к задаче.