Эйлеров путь существует или нет: как проверить условия и при чём тут связность?

Для неориентированного графа (рассматриваем только вершины с ненулевой степенью, изолированные игнорируем):

• Эйлеров цикл существует ⇔ граф связен (по рёбрам) И все вершины имеют чётную степень.
• Эйлеров путь (но не цикл) существует ⇔ граф связен И ровно две вершины имеют нечётную степень (они будут концами пути).
• Нечётных вершин не может быть 1 или 3 — степени в сумме чётны, число нечётных вершин всегда чётно.

Связность обязательна — нельзя обойти рёбра в разных компонентах одним маршрутом. Проверяем связность только по вершинам со степенью > 0.

bool hasEulerPath(int n, vector<int> g[]) {
    int odd = 0, start = -1;
    for (int v = 0; v < n; v++) {
        if (g[v].size() % 2) { odd++; }
        if (!g[v].empty() && start == -1) start = v;
    }
    if (odd != 0 && odd != 2) return false;
    // проверить, что все вершины с deg>0 в одной компоненте (DFS/DSU от start)
    // ... обход, посчитать достижимые с deg>0; сравнить с общим числом таких вершин
    return /* связность по ненулевым вершинам */ true;
}

Для ориентированного графа условия другие: эйлеров цикл ⇔ для каждой вершины indeg == outdeg и граф сильно связен (по ненулевым вершинам); путь ⇔ ровно одна вершина с outdeg - indeg == 1 (старт), одна с indeg - outdeg == 1 (финиш), остальные indeg == outdeg, и связность подходящая.

Сложность проверки O(V+E).