牛牛想知道，他是否能从 
号格子出发回到 号格子。
若能回到 号格子则返回Yes，否则返回No。
[编程题]回路
dfs
只要从1节点开始查找判断，每走过一个点标记一下，并且不能回头踩上一个节点即可。
因为我们只需要判断1节点出来后能不能回去，无论怎么走，之所以用深度是因为1节点每条路的连通图先便利完判断是否回到1，这样时间最多就是遍历所有的点O(n)
代码：
/**
* struct Point {
* int x;
* int y;
* };
*/
class Solution {
public:
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型vector param[0] 为 n，param[1] 为 m
* @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
vector<int> ve[100005];
bool vis[100005];
bool dfs(int u, int fa) {
for (auto &i : ve[u]) {
if (i == fa) continue;
if (i == 1) return true;
if (vis[i]) continue;
vis[i] = true;
if (dfs(i, u)) return true;
}
return false;
}
string solve(vector<int>& param, vector<Point>& edge) {
// write code here
for (auto &i : edge) {
ve[i.x].push_back(i.y);
ve[i.y].push_back(i.x);
}
memset(vis, 0, sizeof(vis));
if (dfs(1, 1)) return "Yes";
else return "No";
}
};
发表于 2020-06-30 13:01:42
回复(16)
解题思路：
① 根据节点的连接关系构建并查集，并查集的每一个子集代表一个连通子图；
② 构建并查集时，不包括1号节点的连接关系，但要记录1号节点的连接关系；
③ 在构建完并查集之后，判断：1号节点是否与并查集的某个连通子图连接了2次。
如果是，则存在回路；否则不存在回路。
参考代码
② 构建并查集时，不包括1号节点的连接关系，但要记录1号节点的连接关系；
③ 在构建完并查集之后，判断：1号节点是否与并查集的某个连通子图连接了2次。
如果是，则存在回路；否则不存在回路。
参考代码
public class Solution {
//并查集
private int[] uninonFindSet;
//连接1号节点的节点集
private HashSet<Integer> nodeToOne;
//连接1号节点的连通子图(用并查集中的头节点代表一个连通子图)
private HashSet<Integer> linkToOne;
public String solve(int[] param, Point[] edge) {
//排除特例
if (param[1] == 0)
return "NO";
//构建并查集
createUnionFindSet(param[0], edge);
//判断1号节点是否存在回路，返回结果
return isCircuit();
}
private String isCircuit() {
//根据1号节点的连接点，将1号节点与连通子图关联起来
for (Integer node : nodeToOne) {
Integer head = findHead(node);
//如果连通子图的头节点已经连接了1号节点，则存在回路；
if (linkToOne.contains(head)) {
return "Yes";
} else {
//否则，在集合中添加连通子图的头节点；
linkToOne.add(head);
}
}
return "No";
}
private void initialize(int n) {
//数组初始化时，默认每个节点的boss为0
uninonFindSet = new int[n + 5];
//连接1的节点默认估计值为 128 个
nodeToOne = new HashSet<Integer>(128);
//连接1的boss节点默认估计值为 128 个
linkToOne = new HashSet<Integer>(128);
}
private void createUnionFindSet(int n, Point[] edge) {
initialize(n);
for (Point p : edge) {
//只记录1号节点的连接点，不参与构建并查集
if (p.x == 1 || p.y == 1) {
//注意：本程序没有考虑 (1,x),(x,1) 这种连接关系
int node = p.x != 1 ? p.x : p.y;
nodeToOne.add(node);
} else if (!isSameHead(p.x, p.y)) {
unionSet(p.x, p.y);
}
}
}
private boolean isSameHead(int x, int y) {
return findHead(x) == findHead(y);
}
private void unionSet(int u, int v) {
int uHead = findHead(u), vHead = findHead(v);
uninonFindSet[uHead] = vHead;
}
//非递归版本：防止测试数据暴栈
private int findHead(int node) {
int head = node;
while (uninonFindSet[head] != 0) {
//真正的头节点 = 头节点的头节点
head = uninonFindSet[head];
}
//并查集扁平化
int curNode = node, nextNode = uninonFindSet[node];
while (nextNode != 0) {
uninonFindSet[curNode] = head;
curNode = nextNode;
nextNode = uninonFindSet[nextNode];
}
return head;
}
} 其它解题思路：广度优先搜索(BFS)
发表于 2020-06-03 22:20:21
回复(4)
我感觉一个很容易忽略的样例是就两个点之间连一条边，这样是不能算作构成一个无向图中的环的，但是如果写dfs时没注意的话是会忽略这种情况的，我感觉自己就是错在这个点所以才会是60%的通过率。这也是为啥要特意判断一下不能再走父节点，即不能1-2-1这样又访问了1然后判定有环，不然一般情况遍历图的话父节点会早就被vis数组标记，我们只判断vis数组就够了。然后我另外一个思路是vis标记边而不是标记点，这样也可以避免上述问题。
标记点：
#define pb push_back
const int maxn = 1e5+5;
class Solution {
public:
vector<int>G[maxn];
bool vis[maxn];
string solve(vector<int>& param, vector<Point>& edge) {
int n = param[0], m = param[1];
for(int i = 0; i < m; i++) {
int u = edge[i].x, v = edge[i].y;
G[u].pb(v);
G[v].pb(u);
}
if(dfs(1, 1)) return "Yes";
else return "No";
}
bool dfs(int u, int f) {
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == f) continue;
if(vis[v]) continue;
vis[v] = true;
if(v == 1 || dfs(v, u)) return true;
}
return false;
}
}; 标记边： #define pb push_back
const int maxn = 1e5+5;
struct Edge{
int id, to;
Edge(int a, int b) {
to = a, id = b;
}
};
class Solution {
public:
vector<Edge>G[maxn];
bool vis[maxn];
string solve(vector<int>& param, vector<Point>& edge) {
int n = param[0], m = param[1];
for(int i = 0; i < m; i++) {
int u = edge[i].x, v = edge[i].y;
G[u].pb(Edge(v, i));
G[v].pb(Edge(u, i));
}
if(dfs(1)) return "Yes";
else return "No";
}
bool dfs(int u) {
for(int i = 0; i < G[u].size(); i++) {
Edge e = G[u][i];
if(vis[e.id]) continue;
vis[e.id] = true;
if(e.to == 1 || dfs(e.to)) return true;
}
return false;
}
};
发表于 2020-07-18 20:56:02
回复(1)
/**
* struct Point {
* int x;
* int y;
* };
*/
class Solution {
public:
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型vector param[0] 为 n，param[1] 为 m
* @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
vector<int> G[100003];
bool vis[100003];
bool DFS(int s, int pre){
for(int i=0;i<G[s].size();i++){
if(G[s][i] == pre)
continue;
if(G[s][i]==1)
return true;
if(!vis[G[s][i]]){
vis[G[s][i]] = true;
if(DFS(G[s][i], s))
return true;
}
}
return false;
}
string solve(vector<int>& param, vector<Point>& edge) {
for(int i=0;i<edge.size();i++){
G[edge[i].x].push_back(edge[i].y);
G[edge[i].y].push_back(edge[i].x);
}
if(DFS(1, 1))
return "Yes";
else
return "No";
}
};
发表于 2020-07-16 01:18:00
回复(0)
string solve(vector<int>& param, vector<Point>& edge) {
int n = param[0];
int m = param[1];
vector<vector<int>> graph(n+1);
for(int i=0;i<m;i++){
int x = edge[i].x;
int y = edge[i].y;
graph[x].push_back(y);
graph[y].push_back(x);
}
//思路，BFS，按照和1号直接相连的点对结点进行标记
//如果遍历的时候发现两个标记不同的点相遇了，说明存在环路
vector<int> visited(n+1,-1);
visited[1] = 0;
queue<int> q;
q.push(1);
while(q.size() > 0){
int currentPoint = q.front();
q.pop();
for(int i=0;i<graph[currentPoint].size();i++){
int nextPoint = graph[currentPoint][i];
if(visited[nextPoint] == -1){
q.push(nextPoint);
if(currentPoint == 1){ //对点进行标记
visited[nextPoint] = i + 1;
}else{
visited[nextPoint] = visited[currentPoint];
}
}else{
if(visited[nextPoint] != visited[currentPoint] && nextPoint != 1){ //不同的点相遇了
return "Yes";
}
}
}
}
return "No";
}
发表于 2020-06-07 10:06:14
回复(0)
import java.util.*;
/*
* public class Point {
* int x;
* int y;
* public Point(int x, int y) {
* this.x = x;
* this.y = y;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型一维数组 param[0] 为 n，param[1] 为 m
* @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
public boolean flag = false;
public String solve (int[] param, Point[] edge) {
ArrayList[] arrayLists = new ArrayList[param[0]+1];
for(int i = 0 ;i<=param[0];i++){
arrayLists[i] = new ArrayList();
}
for(int i = 0 ;i<edge.length;i++){
arrayLists[edge[i].x].add(new SelfEdge(edge[i].y,false));
arrayLists[edge[i].y].add(new SelfEdge(edge[i].x,false));
}
if(solve1(arrayLists,-1,1))
return "Yes";
else
return "No";
}
public boolean solve1(ArrayList[] arrayLists,int st,int des){
for(Object selfEdge:arrayLists[des]){
SelfEdge tem = (SelfEdge) selfEdge;
if(tem.isVisited)
continue;
if(tem.des == 1){
flag=true;
return true;
}else{
if(flag)
return true;
else{
change(arrayLists,des,tem.des);
solve1(arrayLists,des,tem.des);
change1(arrayLists,des,tem.des);
if(flag)
return true;
}
}
}
return false;
}
public void change(ArrayList[] arrayLists,int st,int des){
for(int i =0 ;i<arrayLists[st].size();i++){
SelfEdge selfEdge = (SelfEdge) arrayLists[st].get(i);
if(selfEdge.des == des){
selfEdge.isVisited = true;
arrayLists[st].set(i,selfEdge);
break;
}
}
for(int i = 0 ;i<arrayLists[des].size();i++){
SelfEdge selfEdge = (SelfEdge) arrayLists[des].get(i);
if(selfEdge.des == st){
selfEdge.isVisited = true;
arrayLists[des].set(i,selfEdge);
break;
}
}
}
public void change1(ArrayList[] arrayLists,int st,int des){
for(int i =0 ;i<arrayLists[st].size();i++){
SelfEdge selfEdge = (SelfEdge) arrayLists[st].get(i);
if(selfEdge.des == des){
selfEdge.isVisited = false;
arrayLists[st].set(i,selfEdge);
break;
}
}
for(int i = 0 ;i<arrayLists[des].size();i++){
SelfEdge selfEdge = (SelfEdge) arrayLists[des].get(i);
if(selfEdge.des == st){
selfEdge.isVisited = false;
arrayLists[des].set(i,selfEdge);
break;
}
}
}
}
class SelfEdge{
int des;
boolean isVisited;
public SelfEdge(int des,boolean isVisited){
this.des = des;
this.isVisited = isVisited;
}
} 构造图进行dfs即可。写得太烂了。。
发表于 2021-03-02 18:40:39
回复(0)
我并不是很懂dfs和并查集，去搜了资料，也没看太懂😂😂
我就是按照逐步遍历节点的方式，然后发现可以递归，通过递归完成了这道题，思路我感觉比较清晰，我在代码里注释了一下代码的功能，希望能帮助到大家。
import java.util.*;
/*
* public class Point {
* int x;
* int y;
* }
*/
public class Solution {
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型一维数组 param[0] 为 n，param[1] 为 m
* @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
public String solve (int[] param, Point[] edge) {
// write code here
if(param[1]>100000 || param[0]>100000){
return "No";
}else{
int num = 0;
for(int i = 0;i<edge.length;i++){
if(edge[i].x ==1 || edge[i].y==1){
num++;
}
}
if(num < 2){
return "No";
}
}
//上面是判断两种不符合题意的情况
List<Integer> list = new ArrayList<>();
for(int i=0;i<edge.length;i++){
if(edge[i].x==1){
list.add(i);
}
}//找出所有1能通向的所有y
if(findAll(list,edge)){
return "Yes";
}
return "No";
}
public boolean findAll(List<Integer> list,Point[] edge){
List<Integer> list2 = new ArrayList<>();//用于递归的list
for(int i = 0;i<list.size();i++){
for(int j = 0;j<edge.length;j++){//对每一个可以通向的节点，进行判断
if(edge[j].y == 1){
return true;//通向1，为true
}
if(edge[j].x == edge[list.get(i)].y){
list2.add(j);//通向的不为1，存入list
}
}
}
if(0==list2.size()){//若没有可以通向的节点，返回false
return false;
}
if(findAll(list2,edge)){//递归进入下一个节点
return true;//当递归到最后一个节点时，为true，则会一路返回到顶层
}
return false;//否则返回false到顶层
}
public List<Integer> find(Point[] edge,int n){//查找当前y能通向的所有x
int i;
List<Integer> list = new ArrayList<>();
for(i = 1;i<edge.length;i++){
if(n == edge[i].x){
list.add(i);
}
}
return list;
}
}
编辑于 2020-07-03 21:44:49
回复(1)
【C++】一开始用dfs，莫名超时（心累）
最后改用并查集，终于AC。。吐槽下，牛客OJ的体验真比Leetcode差一个等级TvT
/**
* struct Point {
* int x;
* int y;
* };
*/
class Solution {
public:
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型vector param[0] 为 n，param[1] 为 m
* @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
int find_parent(vector<int>& uf, int node) {
int temp = node;
while (uf[temp] != temp) {
temp = uf[temp];
}
uf[node] = temp;
return temp;
}
void union_node(vector<int>& uf, vector<int>& rank, int a, int b) {
int pa = find_parent(uf, a);
int pb = find_parent(uf, b);
if (pa == pb) return;
if (rank[a]> rank[b]) swap(pa, pb);
uf[pa] = pb;
if (rank[pa] == rank[pb]) ++rank[pb];
}
string solve(vector<int>& param, vector<Point>& edge) {
// write code here
int n = param[0];
int m = param[1];
vector<int> uf(n+1, 0);
vector<int> rank(n+1, 1);
for (int i= 0; i<= n; i++) {
uf[i] = i;
}
vector<int> edge_one;
for (Point e: edge) {
if (e.x == 1) {
edge_one.push_back(e.y);
} else if (e.y == 1) {
edge_one.push_back(e.x);
} else {
union_node(uf, rank, e.x, e.y);
}
}
map<int,int> mmap;
for (int node: edge_one) {
int p = find_parent(uf, node);
if (mmap.find(p) != mmap.end()) {
return "Yes";
}
++mmap[p];
}
return "No";
}
};
发表于 2020-06-21 22:33:06
回复(0)
class Solution
{
public:
static bool dfs(int depth, int node, vector<vector<int>> &list, vector<bool> &isVisited)
{
if (depth > 2 && node == 1) // 遍历回到第1个节点并且至少走过两条边那表明能走通
{
return true;
}
if(isVisited[node] == true) //如果当前点已经被访问过了则返回false
{
return false;
}
isVisited[node] = true; // 标记这个点已经被访问过了，而且无需恢复现场，因为如果访问过没走通就不可能再走通了
for (int i = 0; i < list[node].size(); i++) // 遍历当前node的所有相连节点
{
int connected_node = list[node][i];
if (dfs(depth + 1, connected_node, list, isVisited))
{
return true;
}
}
return false;
}
string solve(vector<int> ¶m, vector<Point> &edge)
{
int n = param[0]; // 格子个数
int m = param[1]; // 边的个数
vector<vector<int>> list(n + 1); // list[i]表示第i个vector中的所有元素与第i个格子相连(存在边)
vector<bool> isVisited(n + 1, false); // isVisited[i]表示第i个node是否已经被访问过
for (int i = 0; i < m; i++)
{
list[edge[i].x].push_back(edge[i].y);
list[edge[i].y].push_back(edge[i].x);
}
return (dfs(0, 1, list, isVisited) ? "Yes" : "No");
}
};
发表于 2024-03-19 23:34:41
回复(0)
/**
* struct Point {
* int x;
* int y;
* Point(int xx, int yy) : x(xx), y(yy) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型vector param[0] 为 n，param[1] 为 m
* @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
string solve(vector<int>& param, vector<Point>& edge) {
const int n = param.front(), m = param.back();
vector<vector<int>> g(n + 1);
for (const auto& e : edge) {
g[e.x].emplace_back(e.y);
g[e.y].emplace_back(e.x);
}
function<bool(int, int)> depth_first_search_algorithm = [&](int curr, int prev) -> bool {
if (curr == 1 && prev != -1)
return true;
// ========== 拆路 ========== (因为每条通道只能走一次。！走过的通道就拆掉算了，防止反复走。管它呢！)
if (prev != -1) {
auto it = find(begin(g[curr]), end(g[curr]), prev);
if (it != end(g[curr])) g[curr].erase(it);
it = find(begin(g[prev]), end(g[prev]), curr);
if (it != end(g[prev])) g[prev].erase(it);
}
// ========== 拆路 ==========
for (const int nxt : g[curr])
if (depth_first_search_algorithm(nxt, curr)) return true;
return false;
};
bool ret = depth_first_search_algorithm(1, -1);
return ret ? "Yes" : "No";
}
};
发表于 2021-07-20 08:41:35
回复(0)
简单易懂的暴力递归法
入口：边的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)
邻接表解法
/*
* function Point(a, b){
* this.x = a || 0;
* this.y = b || 0;
* }
*/
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型一维数组 param[0] 为 n，param[1] 为 m
* @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
var visited = {};
var flag = true;
function solve( param , edge ) {
// write code here
let map = {};
let reachAble = false;
edge.forEach((el)=>{
if(map[el.x] === undefined){
map[el.x] = [el.y];
}else{
map[el.x].push(el.y);
}
if(!reachAble&&el.y===1){
reachAble = true;
}
})
if(!reachAble){
return "No";
}
if(map[1]){
dfs(1,map);
}else{
return "No";
}
if(!flag){
return "Yes";
}
return "No";
}
function dfs(postion,map){
if(postion === 1){
flag = false;
}
if(!flag){
return;
}
let paths = map[postion];
if(!paths){
return;
}
for(let i = 0; i<paths.length;i++){
let po = paths[i];
if(!visited[po]){
visited[po] = true;
dfs(po,map);
}
}
}
module.exports = {
solve : solve
};
发表于 2020-08-02 21:56:59
回复(0)
我用了numpy，但是不对，请各位看看哪里有问题！！！
import numpy as np
a,b=eval(input())
n=a[0]
m=a[1]
k=np.zeros((m,m))
for i in b:
k[i[0]-1][i[1]-1]=1
# print(k)
j=0
while j<m:
i=0
if k[0][j]>=1:
while i<m:
k[0][i]=k[0][i]+k[j][i]
i+=1
j+=1
# print(k)
if k[0][0]>=1:
print("Yes")
else:
print("No")
发表于 2020-07-30 11:14:51
回复(0)
通过 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)
dfs 80%过不去 改的并查集
public class Solution {
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型一维数组 param[0] 为 n，param[1] 为 m
* @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
public String solve (int[] param, Point[] edge) {
// write code here
if(param[0] > 100000 || param[1] > 100000){
return "No";
}
int m = param[0];
int[] un = new int[m+1];
union(edge, un);//不包含1的并查集，将较小的作为根
List<Integer> list = new ArrayList<>();
for(Point p : edge){
if(p.x == 1 || p.y == 1){
int another = p.x == 1 ? p.y : p.x;
list.add(another);
}
}
for(int i=0; i<list.size()-1; i++){
for(int j=i+1; j<list.size(); j++){
int un1 = un[list.get(i)] == 0 ? list.get(i) : un[list.get(i)];
int un2 = un[list.get(j)] == 0 ? list.get(j) : un[list.get(j)];
if(un1 == un2){
return "Yes";
}
}
}
return "No";
}
public void union(Point[] edge, int[] un){
for(Point p : edge){
if(p.x == 1 || p.y == 1){
continue;
}else{
int big = Math.max(p.x, p.y);
int small = Math.min(p.x, p.y);
if(un[big] == 0){
un[big] = un[small] == 0 ? small : un[small];
}else{//都有根的需要对根合并
int smallRoot = small;
int bigRoot = un[big];
while(un[smallRoot] != 0){
smallRoot = un[smallRoot];
}
while(un[bigRoot] != 0){
bigRoot = un[bigRoot];
}
if(smallRoot != bigRoot){
un[Math.max(smallRoot, bigRoot)] = Math.min(smallRoot, bigRoot);
}
}
}
}
for(int i=un.length-1; i>=4; i--){//最后一起找根
if(un[i] != 0){
int temp = un[i];
while(un[temp] != 0){
temp = un[temp];
}
un[i] = temp;
}
}
}
}
发表于 2020-07-09 14:43:05
回复(0)
第一个60%，第二个90...蓝瘦
public class Solution {
/**
* 能回到1号点返回 Yes，否则返回 No
* @param param int整型一维数组 param[0] 为 n，param[1] 为 m
* @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
* @return string字符串
*/
public String solve (int[] param, Point[] edge) {
int n = param[0];
boolean[] visited = new boolean[n+1];
return dfs(1, edge, visited)?"Yes":"No";
}
public boolean dfs(int from, Point[] edge,boolean[] visited) {
int to = 0;
for(int i=0; i<edge.length; i++) {
if(visited[from] || (edge[i].x != from && edge[i].y != from)) continue;
to = edge[i].x == from?edge[i].y:edge[i].x;
visited[from] = true;
if(to == 1 || dfs(to, edge, visited)) return true;
visited[from] = false;
}
return false;
}
} public class Solution { int[] res; public String solve (int[] param, Point[] edge) { int n = param[0],m=param[1]; res = new int[n + 1]; for(int i=0; i<m; i++) { if(union(edge[i].x,edge[i].y)) { return "Yes"; } } return "No"; } public int find(int i) { if(res[i] == 0) return i; return find(res[i]); } public boolean union(int root1,int root2) { if(find(root1) == find(root2)) { if(find(root1) == find(1)) { int next1 = -1,next2 = -1; while(root1 != 1 && res[root1] != 0) { next1 = root1; root1 = res[root1]; } while(root2 != 1 && res[root2] != 0) { next2 = root2; root2 = res[root2]; } if(next1 != next2) return true; } } else { res[root2] = root1; } return false; } }
编辑于 2020-07-08 12:33:27
回复(0)
//不想多了，直接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)
问题信息
难度：
23条回答
42收藏
10084浏览
通过挑战的用户
查看代码-
2023-03-13 09:58:26
-
2023-03-05 16:23:20 -
2023-02-26 11:04:35
-
2022-07-25 16:03:53
-
2022-05-28 20:39:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
