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

题目描述:

幼儿园老师安排小朋友做游戏,现在需要给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
共 17 个回复

DFS解法

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

void dfs(vector<pair<int,int>> &vec, vector<int> &visited, int index)
{
    if(visited[index])
    {
        return;
    }
    visited[index] = 1;
    // search directions
    for(int i = 0; i<vec.size(); i++)
    {
        int n1 = vec[index].first;
        int n2 = vec[index].second;            
        if(!visited[i] && (vec[i].first == n1 || vec[i].first == n2
        || vec[i].second == n1 || vec[i].second == n2))
        {
            dfs(vec,visited, i);
        }
    }  
}

int main()
{
    int N;
    cin>>N;
    map<string,int> cmap;
    vector<pair<int,int>> vec;
    int index = 0;
    while(N--)
    {
        string child, friends;
        // note that
        cin>>child>>friends;
        if(cmap.find(child)==cmap.end()){
            cmap[child] = index++;
            
        }
        if(cmap.find(friends)==cmap.end()){
            cmap[friends] = index++;
        }
        vec.push_back({cmap[child],cmap[friends]});
    }
    
    int size =vec.size();
    int count= 0;
    
    // denote the index of number pair
    vector<int> visited(size,0);

    for(int i = 0; i < size; i++)
    {
         if(!visited[i])
         {
            //  第零行
            dfs(vec,visited,i);
            count++;
         }
    }   
    cout<<"Number" <<count<< endl;

    system("pause");

    return 0;
}

/*
8
Jack Tom
Alice John
Jessica Leonie
Tom  Alice
John Jack
Leonie Jessica
Daoming Chaoyue
Chaoyue Daoming
*/

3

经典路径优化并查集。把两个人放到同一组里,最后统计有几个组就行了呗

2

确定不是昨晚某厂笔试题吗

1

楼主看下这个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

至于并查集的下标如果用数字的话,你可以拿个map存对应名字的下标

1

本质上是求图的联通分量嘛

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
//输入n
//输入n行带空格字符串
//输出分组数
int main()
{
    int N, ans = 0; 
    string s1, s2;
    unordered_map<string, string> name_map;
    cin >> N;
    cin.ignore();
    //放入name_map
    for (int n = 0; n < N; ++n) {
        cin >> s1 >> s2;
        name_map.insert(pair<string, string> (s1, s2)); // name_map[s1] = s2; 
    }
    //打印map大小
    cout << "size of map is"<<name_map.size()<<endl;
    while (!name_map.empty())
    {
        auto it = name_map.begin();
        string key = it->first;
        while (name_map.find(key) != name_map.end())
        {
            string temp = name_map[key];
            name_map.erase(key);
            key = temp;
        }
        ans++;
    }
    cout << ans;
}

这是我一个同学帮忙写出来的,用的hashmap

并查集,或者无向图广度遍历

并查集