Hỏi về bài hasDeadlock trong phần graph trên Codefight Interview

[levana]

Đề 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;
}

[noname00 (HK boy)]

• Có vẻ như bạn đang muốn code DFS? Mình thấy code của bạn hao hao DFS, mà trông cũng hơi dị và phức tạp.
• Đề có đúng là kiểm tra xem có tồn tại 1 circle trong graph này không thế?

[levana]

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

[Gio (Gió)]

Thuật toán có vẻ không sai, nhưng hàm solve không có biến nào tên là path cả.

[levana]

À 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

[noname00 (HK boy)]

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:

void dfs(u):
    count_next = 0
    for v in G[u]:
        if (!visited[u]):
            count_next++
            dfs(v)

    if count_next == 0:
        // Có đáp số

[hungaya (Hung)]

Thuật toán Tarjan

Tarjan's strongly connected components algorithm