Как ускорить проверку оптимальности графа?
Всем привет. Вот такая задача: В стране X есть n городов, которым присвоены номера от 1 до n. Столица страны имеет номер n. Между городами проложены железные дороги.
Однако дороги могут быть двух типов по ширине полотна. Любой поезд может ездить только по одному типу полотна. Условно один тип дорог помечают как R, а другой как B. То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет по этому маршруту проехать. От одного города до другого можно проехать только по маршруту, состоящему исключительно из дорог типа R или только из дорог типа B.
Но это ещё не всё. По дорогам страны X можно двигаться только от города с меньшим номером к городу с большим номером. Это объясняет большой приток жителей в столицу, у которой номер n.
Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B. Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бОльшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя. Выясните, является ли данная вам карта оптимальной.
Ну и дальше задаются вот эти R и B Дороги. В лоб я ее решил, то есть просто тупо нахожу все пути от вершины 1 до N, и смотрю, чтобы там были только одного типа дороги. Но уже на 25 городах работает все безумно долго. Понимаю, что есть какой-то более простой алгоритм, но ничего в голову не приходит. Дайте какую-нибудь идею, в какую сторону думать?
Ответы (3 шт):
Строите ДВА отдельных графа, R и B.
Для каждого обходом в ширину (или любым другим способом) строите таблицу связности, в которой A[i,j]=0 при i<j означает, что путь из i в j не существует, а A[i,j]=1 - существует
Делаете AND соответствующих элементов обеих таблиц между собой. Если результат состоит из одних нулей - карта оптимальная.
Все рёбра графа B переворачиваете и смешиваете с рёбрами графа R. В получившемся общем ориентированном графе ищете циклы. Если есть хоть один, карта не оптимальна.
Решение работает за время пропорциональное суммарному числу рёбер в R и B.
Вот так все заработало. Всем спасибо!
static void dfs(int v)
{
if (flag == 1) return;
visited[v] = 1;
for (int i = 0; i < inpArrayGraph[v].size(); i++)
{
int to = inpArrayGraph[v].get(i);
if (visited[to] == 1)
{
flag = 1;
return;
}
else if (visited[to] == 0) dfs(to);
if (flag == 1) return;
}
visited[v] = 2;
}