回路

[编程题]回路

热度指数：7597 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛在一个迷宫中，迷宫有 $n$ 个格子，有 $m$ 条通道，每条通道连接两个格子 $u$ , $v$ ，编号为 $u$ 的格子与编号为 $v$ 的格子可互相到达，每人每条通道只能走一次。

牛牛想知道，他是否能从 $1$ 号格子出发回到 $1$ 号格子。

若能回到 $1$ 号格子则返回Yes，否则返回No。

示例1

输入

[4, 4],[(1,2), (2, 3), (3,4),(4,1)]

输出

"Yes"

备注:

$1 \leq n \leq 100,000 \quad 0 \leq m \leq 100,000\quad 0 \leq L \leq m$

m对 u, v 互不相同

算法知识视频讲解

Java

Yuerya

简单易懂的暴力递归法

入口：边的x或y为1

递归：每个邻接的节点是否为1？是，yes : 不是，继续找此节点的邻接节点

注意事项：走过的边进行标记不能再走；图是无向图，双向均可走；

import java.util.*;

public class Solution {
    public int n;
    public int m;
    public String solve (int[] param, Point[] edge) {
        if(param.length != 2){
            return "No";
        }
        n = param[0];    //节点
        m = param[1];    //边
        if(edge.length != m || edge.length == 0){
            return "No";
        }
        boolean res = false;
        for(int i = 0; i < m; i++){
            if(edge[i].x == 1){
                if(edge[i].y == 1){
                    return "Yes";
                }
                res = dfs(edge, 1, new boolean[m]);
                if(res){
                    return "Yes";
                }
            }
        }
        return "No";
    }
    public Boolean dfs(Point[] edge, int node, boolean[] visited){
        boolean res = false;
        for(int j = 0; j < m; j++){
            if(!visited[j]){
                if(edge[j].x == node){
                    if(edge[j].y == 1){
                        return true;
                    }else{
                        visited[j] = true;
                        res = dfs(edge, edge[j].y, visited);
                        visited[j] = false;
                        if(res){
                            return true;
                        }
                    }
                }
                if(edge[j].y == node){
                    if(edge[j].x == 1){
                        return true;
                    }else{
                        visited[j] = true;
                        res = dfs(edge, edge[j].x, visited);
                        visited[j] = false;
                        if(res){
                            return true;
                        }
                    }
                }
                
            }
            
        }
        return false;
    }
}

发表于 2021-04-02 01:22:45 回复(0)

Java

codeDorado

通过 dfs 对所有可能进行遍历，早期迷茫在把题目误以为是单向的节点，重新审题后改进后 AC

    /**
     * 能回到1号点返回 Yes，否则返回 No
     *
     * @param param int整型一维数组 param[0] 为 n，param[1] 为 m
     * @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
     * @return string字符串
     */
    boolean[] marked;
    int m;
    Point[] edge;

    public String solve(int[] param, Point[] edge) {
        // write code here
        m = edge.length;
        if (param[1] >= 100000) return "No";
        marked = new boolean[m];
        this.edge = edge;
        for (int i = 0; i < m; i++) {
            if (edge[i].x == 1 || edge[i].y == 1) {
                if (dfs(edge[i], 1, i, 1)) return "Yes";
            }
        }
        return "No";
    }

    /**
     *  判断是否有回路
     * @param point 当前传入的点
     * @param len 最大长度
     * @param index 当前点的索引坐标
     * @param p 上个节点的传入值
     * @return 是否有回路
     */
    public boolean dfs(Point point, int len, int index, int p) {
        if (len == m) return point.y == 1 || point.x == 1;
        if (len > 1 && ((point.x == 1) || (point.y) == 1)) return true;
        marked[index] = true;
        for (int i = 0; i < m; i++) {
            if ((edge[i].x == p || p == edge[i].y) && !marked[i]) {
                if (edge[i].x == p) {
                    if (dfs(edge[i], len + 1, i, edge[i].y)) return true;
                }
                if (edge[i].y == p) {
                    if (dfs(edge[i], len + 1, i, edge[i].x)) return true;
                }
            }
        }
        marked[index] = false;
        return false;
    }

发表于 2020-07-28 21:33:48 回复(0)

Java

Fubuki_0v0

//不想多了，直接dfs

public String solve (int[] param, Point[] edge) {

Set<Point> visited = new HashSet<>();
List<Point>[] map = new ArrayList[param[0]+1];
for(Point p : edge) {
if(map[p.x] == null) {
map[p.x] = new ArrayList<Point>();
}
map[p.x].add(p);
if(map[p.y] == null) {
map[p.y] = new ArrayList<Point>();
}
map[p.y].add(p);
}
if(map[1] == null || map[1].get(0) == null) {
return "No";
}
List<Point> stack = new ArrayList<>();
List<Integer> pstack = new ArrayList<>();
for(Point li : map[1]) {
stack.add(li);
pstack.add(li.x==1?li.y:li.x);
}
while(!stack.isEmpty()) {
Point l = stack.remove(stack.size()-1);
int p = pstack.remove(pstack.size()-1);
visited.add(l);
for(Point li : map[p]) {
if(visited.contains(li)) {
continue;
}
int n = li.x==p?li.y:li.x;
if(n == 1) {
return "Yes";
}
stack.add(li);
pstack.add(n);
}
}
return "No";
}

发表于 2020-07-04 17:07:16 回复(0)