返回公司

// 标准bfs

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        // T组数据
        for (int i = 0; i < T; i++) {
            // n个点，m条边
            int n = sc.nextInt();
            int m = sc.nextInt();

            HashSet<Integer> visited = new HashSet<>();
            Map<Integer, List<Integer>> neighbors = new HashMap<>();
            for (int j = 0; j < n; j++) {
                neighbors.put(j + 1, new ArrayList<>());
            }

            for (int j = 0; j < m; j++) {
                int point1 = sc.nextInt();
                int point2 = sc.nextInt();
                List<Integer> list1 = neighbors.get(point1);
                list1.add(point2);
                neighbors.put(point1, list1);
                List<Integer> list2 = neighbors.get(point2);
                list2.add(point1);
                neighbors.put(point2, list2);
            }

            boolean flag = false;

            int length = 0;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(1);
            while (!queue.isEmpty() && !flag) {
                int size = queue.size();
                length++;
                for (int j = 0; j < size; j++) {
                    int point = queue.poll();
                    if (point == n && length == 3) {
                        flag = true;
                    }
                    visited.add(point);
                    List<Integer> nexts = neighbors.get(point);
                    for (int k = 0; k < nexts.size(); k++) {
                        int next = nexts.get(k);
                        if (!visited.contains(next)) {
                            queue.add(next);
                        }
                    }
                }
            }
            if (flag){
                System.out.println("POSSIBLE");
            }else {
                System.out.println("IMPOSSIBLE");
            }
        }
    }

}  

C++ bfs求最短路

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
vector<int> g[maxn];
int inq[maxn];

bool solve() {
    int n, m, u, v;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) g[i].clear();
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(inq, 0, sizeof(inq));
    queue<int> q;
    q.push(1);
    inq[1] = true;
    int dis = 0;
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            int cur = q.front(); q.pop();
            if (cur == n) return true;
            for (int v : g[cur]) {
                if (inq[v]) continue;
                inq[v] = true;
                q.push(v);
            }
        }
        if (dis++ == 2) break;
    }
    return false;
}

int main() {
    int t; cin >> t;
    while (t--) {
        if (solve()) puts("POSSIBLE");
        else puts("IMPOSSIBLE");
    }
    return 0;
}

T=int(input())
for t in range(T):
    n,m=list(map(int,input().split()))
    s1,s2=set(),set()
    for i in range(m):
        a,b=list(map(int,input().split()))
        if a==1:
            s1.add(b)
        if b==n:
            s2.add(a)
    if len(s1&s2)>0 or n in s1 or 1 in s2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;


class Point {
    int index;
    List<Point> neighbor;
    boolean alreadyPassed = false;

    public Point(int index) {
        this.index = index;
        this.neighbor = new ArrayList<>();
    }
}

public class Main {
    static boolean res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            res = false;
            int n = sc.nextInt();
            int m = sc.nextInt();
            //Point[]数组用来帮助保存相邻关系
            Point[] points = new Point[n];
            for (int j = 0; j < n; j++) {
                points[j] = new Point(j + 1);
            }
            for (int j = 0; j < m; j++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                points[a].neighbor.add(points[b]);
                points[b].neighbor.add(points[a]);
            }
            points[0].alreadyPassed = true;
            recur(points[0], 2, n);
            System.out.println(res ? "POSSIBLE" : "IMPOSSIBLE");
        }
    }

    private static void recur(Point point, int count, int n) {
        if (res || count < 0) return;
        if (point.index == n) {
            res = true;
            return;
        }
        for (Point neighbor : point.neighbor) {
            if (neighbor.alreadyPassed) continue;
            neighbor.alreadyPassed = true;
            recur(neighbor, count - 1, n);
            neighbor.alreadyPassed = false;
        }
    }
}

import java.lang.reflect.Array;
import java.util.*;

public class Main {

    static class State{
        public int id;
        public int dist;
        public State(int id,int dist) {
            this.id=id;
            this.dist=dist;
        }
    }
    static List<Integer>[] grapLists;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int l=0;l<t;l++) {
            int n=sc.nextInt();
            int m=sc.nextInt();
            grapLists=new List[n+1];
            for(int i=1;i<=n;i++) {
                grapLists[i]=new ArrayList<>();
            }
            for(int i=0;i<m;i++) {
                int a=sc.nextInt();
                int b=sc.nextInt();
                grapLists[a].add(b);
                grapLists[b].add(a);
            }
            int[] distTo=new int[n+1];
            Arrays.fill(distTo, Integer.MAX_VALUE);
            distTo[1]=0;
            PriorityQueue<State> pq=new PriorityQueue<>(new Comparator<State>() {
                @Override
                public int compare(State o1, State o2) {
                    return o1.dist-o2.dist;
                }
            });
            pq.add(new State(1,0));
            while (!pq.isEmpty()){
                State poll = pq.poll();
                if(poll.dist>2){
                    System.out.println("IMPOSSIBLE");
                    break;
                }
                if(poll.id==n){
                    System.out.println("POSSIBLE");
                    break;
                }
                if(distTo[poll.id]<poll.dist){
                    continue;
                }
                List<Integer> list = grapLists[poll.id];
                for (Integer integer : list) {
                    int newDist=poll.dist+1;
                    if(newDist<distTo[integer]){
                        distTo[integer]=newDist;
                        pq.add(new State(integer,newDist));
                    }
                }
            }
        }
        sc.close();
    }
}

图的遍历