Find circle road in list of roads if exists (there may be 1 or 0 occurrence of circle road)

app.dart

import 'package:simple_playground/algo/find_circle_road.dart';


void main() {
  print(findCircularRoad(input1));
  print(findCircularRoad(input2));
  print(findCircularRoad(input3));
  print(findCircularRoad(input4));
}

List<Road> input1 = [
  Road('m', 'y'),
  Road('mu', 'y'),
  Road('mu', 'nord_pole'),
  Road('m', 'my'),
  Road('y', 'r'),
  Road('r', 's'),
  Road('m', 's'),
];

List<Road> input2 = [
  Road('m', 'y'),
  Road('y', 'r'),
  Road('r', 'm'),
];

List<Road> input3 = [
  Road('m', 'y'),
  Road('y', 'r'),
];

List<Road> input4 = [
  Road('m', 'y'),
  Road('mu', 'y'),
  Road('m', 'my'),
  Road('y', 'r'),
  Road('r', 's'),
  Road('m', 's'),
  Road('m', 'n'),
  Road('m', 'x'),
  Road('z', 'x'),
];

find_circle_road.dart

class Road {
  final String city1;
  final String city2;
  Road(this.city1, this.city2);

  @override
  String toString() {
    return 'Road{$city1-🚗-$city2}';
  }
}

List<Road> findCircularRoad(List<Road> roads) {
  _removeDeadEndRoadsRecursive(roads);
  return roads;
}

void _removeDeadEndRoadsRecursive(List<Road> roads) {
  var deadEndCities = _getDeadEndCities(roads);

  final roadsCopy = List.from(roads);

  for (Road r in roadsCopy) {
    if (_isRoadDeadEnd(r, deadEndCities)) {
      roads.remove(r);
    }
  }
  if (roadsCopy.length == roads.length) {
    return;
  } else {
    _removeDeadEndRoadsRecursive(roads);
  }
}

bool _isRoadDeadEnd(Road road, Set<String> deadEndCities) =>
    deadEndCities.contains(road.city1) || deadEndCities.contains(road.city2);

Set<String> _getDeadEndCities(List<Road> input) {
  Set<String> result = Set();
  final map = _getAllCitiesOccurrences(input);
  map.keys.forEach((k) {

    if (map[k] == 1) {
      result.add(k);
    }
  });
  return result;
}

Map<String, int> _getAllCitiesOccurrences(List<Road> input) {
  Map<String, int> map = {};

  for (Road r in input) {
    if (map.containsKey(r.city1)) {
      map[r.city1] += 1;
    } else {
      map[r.city1] = 1;
    }
    if (map.containsKey(r.city2)) {
      map[r.city2] += 1;
    } else {
      map[r.city2] = 1;
    }
  }
  return map;
}

pseudocode

Алгоритм:

1) из списка дорог удаляем рекурсивно удаляем тупиковые (например в input1 в первом прогоне удалится Road('mu', 'nord_pole') и
  Road('m', 'my'), во втором Road('mu', 'y')
2) оставшиеся в списке дороги и есть КАД

Пояснения:

find_circle_road.dart - реализация 
app.dart - проверка

output:

[Road{m-🚗-y}, Road{y-🚗-r}, Road{r-🚗-s}, Road{m-🚗-s}]
[Road{m-🚗-y}, Road{y-🚗-r}, Road{r-🚗-m}]
[]
[Road{m-🚗-y}, Road{y-🚗-r}, Road{r-🚗-s}, Road{m-🚗-s}]