207. Course Schedule
Problem's Link
----------------------------------------------------------------------------
Mean:
给定一个有向图，判断是否存在top_sort序列.
analyse:
转换为：判断是否存在环.
若存在环，肯定不能找到top_sort序列.
判环的方式有很多：SPFA，top_sort，BFS，DFS...随便选一种就行.
Time complexity: O(N)
view code
我的代码：
);
)
) ;;;
}
/*
)
) ;;;
}
/*
*/
下面是discuss区的代码，看了一下，感觉还有很多可以优化的地方，我在代码中注释出来了.
代码1：
; ); ; ; ; ;
for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
-- d[*it];
}
return true;
}
for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
-- d[*it];
}
return true;
}
代码2：
; ;
;
);
for (auto neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
};
;
);
for (auto neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
};