讨论/技术交流/无意间看到的一道题/
无意间看到的一道题

题目描述:

幼儿园老师安排小朋友做游戏,现在需要给N个小朋友进行分组,老师让每个同学写一个名字,代表这位小朋友想和谁分到一组,请问老师在满足所有小朋友意思的情况下,最多可以将班级分为几组?

输入描述:

第一行输入N,0<N<=100000
接下来是N行代表每个小朋友希望和谁分到一组,如:”John Jack”,代表John希望和Jack分到一组,两个名字之间以空格分割,名字本身不存在空格。

输出描述:

分组的最多数量

输入:

6
Jack Tom
Alice John
Jessica Leonie
Tom Alice
John Jack
Leonie Jessica

输出:

2

2

楼主看下这个java可以吗?你需要自己写parse input的逻辑。。。

public class Main {
    int[] parent;
    public static void main(String[] args) {
        int N = 6;
        String[] groups = new String[]{"Jack Tom", "Alice John", "Jessica Leonie", "Tom Alice", "John Jack", "Leonie Jessica"};
        Main testMain = new Main();
        System.out.println(testMain.findNumGroups(N, groups));
    }
    
    public int findNumGroups(int N, String[] groups){
        int n = groups.length;
        //not all groups are specified..
        if(n != N) return(0);
        parent = new int[N];
        for(int i = 0; i < N; i++) parent[i] = i;
        Map<String, Integer> map = new HashMap<>();
        int ii = 0;
        for(String s: groups){
            String[] ab = s.split(" ");
            map.put(ab[0], ii++);
        }
        for(String s: groups){
            String[] ab = s.split(" ");
            int a = map.get(ab[0]);
            int b = map.get(ab[1]);
            union(a, b);
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < N; i++){
            set.add(find(i));
        }
        return(set.size());
    }
    public void union(int x, int y){
        parent[find(x)] = find(y);
    }
    public int find(int x){
        if(parent[x] != x) parent[x] = find(parent[x]);
        return(parent[x]);
    }
}
1
展开全部 18 讨论