小A最多会新认识的多少人

[编程题]小A最多会新认识的多少人

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

小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？

输入描述:

第一行聚会的人数：n（n>=3 & n<10000）；
第二行小A的编号: ai（ai >= 0 & ai < n)；
第三互相认识的数目: m（m>=1 & m
< n(n-1)/2）；
第4到m+3行为互相认识的对，以','分割的编号。

输出描述:

输出小A最多会新认识的多少人？

示例1

输入

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

输出

算法知识视频讲解

Java

WSharkCoder

图的数据结构必须邻接矩阵，简直裂开！

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        int ai = Integer.parseInt(reader.readLine());
        int m = Integer.parseInt(reader.readLine());

        int[][] pairs = new int[m][2];
        for (int i = 0; i < m; i++) {
            String[] D = reader.readLine().split(",");
            pairs[i][0] = Integer.parseInt(D[0]);
            pairs[i][1] = Integer.parseInt(D[1]);

        }
        Map<Integer, ArrayList<Integer>> A = new HashMap<>();
        for (int[] pair : pairs) {
            if (!A.containsKey(pair[0])) {
                A.put(pair[0], new ArrayList<>());
            }
            if (!A.containsKey(pair[1])) {
                A.put(pair[1], new ArrayList<>());
            }
            A.get(pair[0]).add(pair[1]);
            A.get(pair[1]).add(pair[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> hasVisited = new HashSet<>();
        queue.add(ai);
        int res = 0;
        while (!queue.isEmpty()) {
            int idx = queue.poll();
            if (hasVisited.contains(idx)) {
                continue;
            }
            if (A.get(idx) != null) {
                for (int num : A.get(idx)) {
                    queue.add(num);
                }
            }
            hasVisited.add(idx);
            res++;
        }
        if (A.get(ai) != null) {
            res -= A.get(ai).size();
        }
        res-=1;
        writer.write(String.valueOf(res));

        reader.close();
        writer.close();
    }
}

发表于 2021-08-25 01:19:19 回复(0)

Java

笔寞

//并查集求联通块内的点数量，但是要减去时间相连的，用hashset存一下就好了
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    static int N = 10010, n, start, m;
    static int[] p = new int[N], cnt = new int[N];

    static int find(int x){
        if(p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); start = in.nextInt(); m = in.nextInt();

        for(int i = 0; i < n; i ++) p[i] = i;
        HashSet<Integer> set = new HashSet<>();
        Arrays.fill(cnt, 1);
        for(int i = 1; i <= m; i ++){
            String[] arr = in.next().split(",");
            int a = Integer.parseInt(arr[0]), b = Integer.parseInt(arr[1]);
            if(a == start || b == start){
                set.add(a); set.add(b);
            }
            int pa = find(a),  pb = find(b);
            if(pa != pb){
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
        }
        System.out.println( cnt[find(start)] - set.size());
    }

}

发表于 2021-08-09 21:22:19 回复(0)

Java

何止hz

图的广度优先搜索。小A跟其他人都不认识的时候，代码需要加一行判断才能通过，但测试用例没有考虑这种情况。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @Author: coderjjp
 * @Date: 2020-05-07 19:40
 * @Description: 小A最多会新认识的多少人
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        boolean flag[] = new boolean[n];
        int a = Integer.valueOf(br.readLine());
        int m = Integer.valueOf(br.readLine());
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        String line[];
        int f, t;
        while (m-- > 0){
            line = br.readLine().split(",");
            f = Integer.valueOf(line[0]);
            t = Integer.valueOf(line[1]);
            if (graph.get(f) == null){
                ArrayList<Integer> val = new ArrayList<>();
                val.add(t);
                graph.put(f, val);
            }else
                graph.get(f).add(t);
            if (graph.get(t) == null){
                ArrayList<Integer> val = new ArrayList<>();
                val.add(f);
                graph.put(t, val);
            }else
                graph.get(t).add(f);
        }
//        if (graph.get(a) == null){
//            System.out.println(0);
//            return;
//        }
        ArrayList<Integer> res = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        q.offer(a);
        flag[a] = true;
        while (!q.isEmpty()){
            int node = q.poll();
            res.add(node);
            for (int i : graph.get(node))
                if (!flag[i]){
                    q.offer(i);
                    flag[i] = true;
                }
        }
        System.out.println(res.size() - 1 - graph.get(a).size());
    }
}

编辑于 2020-05-07 21:19:31 回复(0)