N — до 10⁵, а у тебя объявлена матрица смежности до 5000. При попытки перейти в вершину с индексом больше 5000, программа обращается в неизвестную область памяти, и происходит непонятно что.

Позвольте для начала разнести некоторые вещи из вашего кода в пух и прах. Цель — рассказать, почему какие-то вещи делать не надо и как надо делать вместо этого.

1. Начну с хорошего: спасибо, что выложили подсвеченную версию, а не просто скопировали код без оформления. На будущее: еще можно давать ссылку на посылки (кнопка с логотипом Codeforces в окне редактирования -> submission, номер посылки можно скопировать со страницы "попытки".
2. Теперь то, что можно сделать лучше, основная претензия: отступы и форматирование кода. Когда вы хотите, чтобы ваш код кто-то прочитал, в том числе вы сами через десять минут (а вы просите помощи, то есть точно этого хотите), его следует оформлять в соответствии с некоторыми общепринятыми стандартами. Например, принято отделять все блоки кода (внутри фигурных скобок) отступами в несколько пробелов (некоторые используют вместо пробелов символ табуляции, но мешать точно не надо — у всех табуляцию имеет разную ширину). Подробнее можно посмотреть тут. Стилей расстановки отступов и скобок несколько, самые популярные — K&R и Олман, выберите один (какой больше нравится) и придерживайтесь его в коде. Почему так делать хорошо и нужно: стандартный вид кода делает чтение намного легче, например, я могу чисто визуально определить, внутри каких if'ов и циклов будет лежать каждая строчка и просто пропустить те, которые мне неинтересны. При отсутствии форматирования я вынужден читать каждый символ, что раздражает. Уважайте тех, кто хочет вам помочь: сделайте код легче для чтения. Если вы пишете в среде разработки (вроде Code::Blocks или Visual Studio), наверняка есть стандартная команда "отформатировать код". Если почему-то принципиально не хотите писать, как принято, можете пользоваться онлайн-форматтером перед вставкой кода, например, тут. Вот пример вашего кода после форматирования (вот этим форматтером, на который я сослался). Читать намного легче: все команды на разных строках, чётко видна структура dfs: что-то содержательное происходит только в случае cat[i] <= k, причём сначала идёт цикл по всем вершинам, удовлетворяющим какому-то условию, а потом как-то модифицируется некоторая переменная c. Таким образом человек, не знающий решения задачи и хода ваших мыслей, может его хотя бы попробовать восстановить.
3. В C++ есть тип void, который можно указывать, когда функция ничего не возвращает. Например: void dfs(int i). Тогда возврат из середины функции пишется просто командой return;, а в конце функции можно вообще return; не ставить — он сам поставится. С функцией main так нельзя — она особенная и должна возвращать int. Опять же, ради повышения читаемости: если я вижу, что dfs возвращает некоторое значение, то я предполагаю, что оно где-то используется и очень удивляюсь, когда вижу return 0; и то, что результат вызовов dfs(1) и dfs(j) никак не используется.
4. Глобальные переменные простых типов (int, double) и массивы из них в C++ по умолчанию инициализириются нулями (в отличие от локальных, в которых может быть любая фигня и поэтому надо инициализировать явно: int x = 0). Поэтому, в частности, вам необязательно их инициализировать нулями. Более того, конструкция int a[10] = { x } вовсе не заполняет массив иксами, как может показаться на первый взгляд — пример. Происходит что-то менее очевидное: все указанные в скобках элементы заполняются указанными значениями, а остальные — значениями по умолчанию. Запись int a[10] = { 0 } притворяется, будто бы она обозначает "заполни всё нулями", хотя это не так, поэтому так писать не стоит. Если у вас глобальный массив — оставьте его вообще без инициализации, он будет заполнен нулями. Если локальный (или хотите явно проинициализировать глобальный массив) — напишите int a[10] = {} — в этом случае все элементы точно заполнятся значениями по умолчанию.
5. Если у вас какая-то константа, наделённая смыслом, встречается в коде хотя бы один раз (особенно если это константа из условия или ограничения на вход) — обязательно оформляйте это в отдельную константу, а не копируйте каждый раз. Почему: при копипасте есть риск ошибиться; вам наверняка потом захочется это константу исправить (в отладочных целях, например), и исправлять в одном месте намного проще, чем искать везде по коду (опять же, есть риск ошибиться при исправлении). Как надо: заводите константу с говорящим именем (например, MAX_N или MAX_VERTICES) и используете её. При этом не стоит использовать одну константу для разных по смыслу вещей: если у вас 1000 вершин и 1000 рёбер (и вы хотите хранить рёбра в списке), заведите разные константы: возможно, вы вспомните, что на самом деле вам надо хранить каждое ребро дважды (в одну сторону и в другую) или нужно добавлять дополнительные рёбра в граф. Например:

const int MAX_N = 5000;
int cat[MAX_N];
bool color[MAX_N];
int a[MAX_N][MAX_N];

Собственно, последняя рекомендация оказалась бы для вас спасительной: у вас размер массива cat не такой, как для остальных (14763809).