01/10/2018, 12:01
Hỏi về bài hasDeadlock trong phần graph trên Codefight Interview
Đề như vầy còn đây là bài giải của em. Em chạy được test 1 và 2, còn mấy test khác thì ouput: empty. Có chạy mấy test đó trên codeblocks + vs2017 thì đều chạy ra đúng kết quả, không hiểu sao đem lên web thì ra empty. Có bác nào chỉ giúp em chỗ sai, nếu không thì cho em xin solution cũng được ạ. Tìm trên gg cũng ko ra solution bài này. Em cảm ơn.
bool solve(vector<vector<int>> connections,int currentNode,int startNode, vector<int> path) {
if (currentNode== startNode&&path.size()>1) {
return true;
}
else {
for (int j = 0; j < connections[currentNode].size(); j++) {
path.push_back(connections[currentNode][j]);
if (solve(connections, connections[currentNode][j], startNode, path)) {
return true;
}
path.pop_back();
}
}
return false;
}
bool hasDeadlock(vector<vector<int>> connections) {
vector<int> path;
for (int i = 0; i < connections.size(); i++){
path.push_back(i);
if (solve(connections, i, i, path))
return true;
path.pop_back();
}
return false;
}
Bài liên quan
thuật toán của em là: duyệt tất cả đỉnh rồi từ đỉnh đó duyệt DFS như bác nói nếu duyệt mà tới lại điểm ban đầu thì return true, không thì false. Mà nó chỉ cần 1 vòng thôi (ví dụ có 5 đỉnh chỉ cần tồn tại 1 2 3 1 là đc rồi) ko cần phải như hamilton. Vậy thôi ạ. Em thử các test trong web đưa ra ở ide thì đúng cả nhưng khi lên web thì ra empty. Bác có solution thì quăng em, em submit qua bài mới cũng đc. Cảm ơn
Thuật toán có vẻ không sai, nhưng hàm
solvekhông có biến nào tên làpathcả.À sorry bác, ban đầu em để hamilton, mà do nó ko phải là hamilton nên em đổi thành path rồi mới up lên đây ^^ sr sr. Mà cái đó ko ảnh hưởng gì đâu bác. Nó vẫn sai từ test 3 trở đi
Thuật toán thì đơn giản nhưng mà code phức tạp quá. Suy nghĩ “chân phương” thôi:
Thuật toán Tarjan
en.m.wikipedia.org
Tarjan's strongly connected components algorithm
Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's algorithm is named for its inventor, Robert Tarjan. The algorithm takes a directed graph as input, and produces a partition of the graph's vertices into the graph's strongly connected components. Each vertex of the graph appears in...