美团2024春招第一场笔试(技术) - 小美的朋友关系_小美的朋友关系java

作者：黑客灵魂 | 2024-07-09 11:34:00

踩

小美的朋友关系java

先用Java尝试写了一遍，一直超时，然后，让GPT 1:1 翻译成C++通过了。是我Java不配吗？还是我Java写的太臭了？

Java 输入输出 printf 和 scanner 背大锅。换成 BufferedReader 和 BufferedWriter 是可以通过的。Java AC代码如下：

import java.io.*;
import java.util.*;

public class Main {

    static Map<Integer, Integer> roots = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nmq = br.readLine().split(" ");
        int n = Integer.parseInt(nmq[0]);
        int m = Integer.parseInt(nmq[1]);
        int q = Integer.parseInt(nmq[2]);

        int[][] operator = new int[q][3];
        Map<Integer, Set<Integer>> map = new HashMap<>();

        for (int i = 0; i < m; i++) {
            String[] uv = br.readLine().split(" ");
            int u = Integer.parseInt(uv[0]);
            int v = Integer.parseInt(uv[1]);
            roots.put(u, u);
            roots.put(v, v);
            map.computeIfAbsent(u, key -> new HashSet<>()).add(v);
            map.computeIfAbsent(v, key -> new HashSet<>()).add(u);
        }

        for (int i = 0; i < q; i++) {
            String[] opr = br.readLine().split(" ");
            int op = Integer.parseInt(opr[0]);
            int u = Integer.parseInt(opr[1]);
            int v = Integer.parseInt(opr[2]);

            if (op == 1) {
                if (!map.containsKey(u) || !map.containsKey(v) || !map.get(u).contains(v)) {
                    continue;
                } else {
                    map.get(u).remove(v);
                    map.get(v).remove(u);
                }
            }
            operator[i][0] = op;
            operator[i][1] = u;
            operator[i][2] = v;
        }

        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            int u = entry.getKey();
            Set<Integer> uSet = entry.getValue();
            for (int us : uSet) {
                unionSets(u, us);
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            int op = operator[i][0], u = operator[i][1], v = operator[i][2];
            if (op == 1) {
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    continue;
                }
                unionSets(u, v);
            } else if (op == 2) {
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    ans.add("No");
                    continue;
                }
                if (isInOneSet(u, v)) {
                    ans.add("Yes");
                } else {
                    ans.add("No");
                }
            }
        }

        for (int i = ans.size() - 1; i >= 0; i--) {
            bw.write(ans.get(i) + "\n");
        }

        bw.flush();
    }

    public static int find(int i) {
        if (roots.get(i) == i) {
            return i;
        }
        roots.put(i, find(roots.get(i)));
        return roots.get(i);
    }

    public static boolean isInOneSet(int i, int j) {
        return find(i) == find(j);
    }

    public static void unionSets(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj) {
            roots.put(fj, fi);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

第一次超时Java代码如下：

import java.util.*;

public class Main {
    public static Map<Integer, Integer> roots;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        int[][] operator = new int[q][3];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        roots = new HashMap<>();

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            roots.put(u, u);
            roots.put(v, v);
            if (!map.containsKey(u)) {
                Set<Integer> fri = new HashSet<>();
                fri.add(v);
                map.put(u, fri);
            } else {
                map.get(u).add(v);
            }
            if (!map.containsKey(v)) {
                Set<Integer> fri = new HashSet<>();
                fri.add(u);
                map.put(v, fri);
            } else {
                map.get(v).add(u);
            }
        }

        for (int i = 0; i < q; i++) {
            int op = sc.nextInt(), u = sc.nextInt(), v = sc.nextInt();
            if (op == 1) {
                if (!map.containsKey(u) || !map.containsKey(v) || !map.get(u).contains(v)) {
                    continue;
                } else {
                    map.get(u).remove(v);
                    map.get(v).remove(u);
                }
            }
            operator[i][0] = op;
            operator[i][1] = u;
            operator[i][2] = v;
        }

        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            int u = entry.getKey();
            Set<Integer> uSet = entry.getValue();
            for (int us : uSet) {
                union(u, us); // 并
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            int op = operator[i][0], u = operator[i][1], v = operator[i][2];
            if (op == 1) {
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    continue;
                }
                union(u, v);
            } else if (op == 2){
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    ans.add("No");
                    continue;
                }
                if (isInOneSet(u, v)) {
                    ans.add("Yes");
                } else {
                    ans.add("No");
                }
            }
        }

        for (int i = ans.size() - 1; i >= 0; i--) {
            System.out.println(ans.get(i));
        }
    }

    public static int find(int i) {
        if (roots.get(i) == i) {
            return i;
        }
        int j = find(roots.get(i));
        roots.put(i, j);
        return j;
    }

    public static boolean isInOneSet(int i, int j) {
        return find(i) == find(j);
    }

    public static void union(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj) {
            roots.put(fj, fi);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

GPT翻译的C++代码如下（AC）：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<int, int> roots;

int find(int i) {
    if (roots[i] == i) {
        return i;
    }
    return roots[i] = find(roots[i]);
}

bool isInOneSet(int i, int j) {
    return find(i) == find(j);
}

void unionSets(int i, int j) {
    int fi = find(i);
    int fj = find(j);
    if (fi != fj) {
        roots[fj] = fi;
    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> operatorVec(q, vector<int>(3));
    unordered_map<int, unordered_set<int>> map;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        roots[u] = u;
        roots[v] = v;
        map[u].insert(v);
        map[v].insert(u);
    }

    for (int i = 0; i < q; i++) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            if (map.find(u) == map.end() || map.find(v) == map.end() ||
                    map[u].find(v) == map[u].end()) {
                continue;
            } else {
                map[u].erase(v);
                map[v].erase(u);
            }
        }
        operatorVec[i][0] = op;
        operatorVec[i][1] = u;
        operatorVec[i][2] = v;
    }

    for (auto& entry : map) {
        int u = entry.first;
        unordered_set<int>& uSet = entry.second;
        for (int us : uSet) {
            unionSets(u, us);
        }
    }

    vector<string> ans;
    for (int i = q - 1; i >= 0; i--) {
        int op = operatorVec[i][0], u = operatorVec[i][1], v = operatorVec[i][2];
        if (op == 1) {
            if (roots.find(u) == roots.end() || roots.find(v) == roots.end()) {
                continue;
            }
            unionSets(u, v);
        } else if (op == 2){
            if (roots.find(u) == roots.end() || roots.find(v) == roots.end()) {
                ans.emplace_back("No");
                continue;
            }
            if (isInOneSet(u, v)) {
                ans.emplace_back("Yes");
            } else {
                ans.emplace_back("No");
            }
        }
    }

    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

第二次：Java代码改的优雅了一些，多过了一个样例，没啥用，哎，代码如下：

import java.util.*;

public class Main {

    static Map<Integer, Integer> roots = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),  m = sc.nextInt(), q = sc.nextInt();
        int[][] operator = new int[q][3];
        Map<Integer, Set<Integer>> map = new HashMap<>();

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            roots.put(u, u);
            roots.put(v, v);
            map.computeIfAbsent(u, key -> new HashSet<>()).add(v);
            map.computeIfAbsent(v, key -> new HashSet<>()).add(u);
        }

        for (int i = 0; i < q; i++) {
            int op = sc.nextInt(), u = sc.nextInt(), v = sc.nextInt();
            if (op == 1) {
                if (!map.containsKey(u) || !map.containsKey(v) || !map.get(u).contains(v)) {
                    continue;
                } else {
                    map.get(u).remove(v);
                    map.get(v).remove(u);
                }
            }
            operator[i][0] = op;
            operator[i][1] = u;
            operator[i][2] = v;
        }

        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            int u = entry.getKey();
            Set<Integer> uSet = entry.getValue();
            for (int us : uSet) {
                unionSets(u, us);
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            int op = operator[i][0], u = operator[i][1], v = operator[i][2];
            if (op == 1) {
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    continue;
                }
                unionSets(u, v);
            } else if (op == 2) {
                if (!roots.containsKey(u) || !roots.containsKey(v)) {
                    ans.add("No");
                    continue;
                }
                if (isInOneSet(u, v)) {
                    ans.add("Yes");
                } else {
                    ans.add("No");
                }
            }
        }

        for (int i = ans.size() - 1; i >= 0; i--) {
            System.out.println(ans.get(i));
        }
    }

    public static int find(int i) {
        if (roots.get(i) == i) {
            return i;
        }
        roots.put(i, find(roots.get(i)));
        return roots.get(i);
    }

    public static boolean isInOneSet(int i, int j) {
        return find(i) == find(j);
    }

    public static void unionSets(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj) {
            roots.put(fj, fi);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/802276