4/7华为软件实习笔试第一题：给N个小朋友分组

给N个字符串分组，
第一行输入N(0<N<=100000),接下来N行每行给出两个字符串（0<名字长度<=20），表示该两个字符串为一组
输出最多的组数

最讨厌这种乍一看很简单结果越写越难的题了。。。两种方法的核心都是先判断两个字符串是否已经存在在一个小组内，如果两个在同一个小组，则do nothing；如果在不同的小组，则合并小组；如果只有一个在小组内，则直接把另一个字符串添加进该小组；否则就新建一个小组。

方法一：用vector<set>记录</set>

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin>>N;
    string a,b;
    vector< set<string> > record;
    for(int i=0;i<N;i++){
        cin>>a;
        cin.get();
        cin>>b;
        cin.get();
        //cout<<a<<" "<<b<<endl;
        bool done_flag=false;
        for(int i=0;i<record.size() && !done_flag;i++){
            if(record[i].find(a) != record[i].end() || record[i].find(b) != record[i].end()){
                if(record[i].find(a) != record[i].end() && record[i].find(b) != record[i].end()){
                    done_flag=true;
                    break;
                }
                if(record[i].find(b) != record[i].end()) swap(a,b);
                for(int j=i+1;j<record.size();j++){
                if(record[j].find(b) != record[j].end()){
                        record[i].insert(record[j].begin(),record[j].end());
                        record.erase(record.begin()+ j);
                        done_flag=true;
                        break;
                    }
                }
            }
        }
        if(!done_flag){
            set<string> tmp;
            tmp.insert(a);tmp.insert(b);
            record.push_back(tmp);
        }
    }
    cout<<record.size()<<endl;
    return 0;
}

方法二：链表

#include <bits/stdc++.h>
using namespace std;
/*
定义了一个链表用来存一个组的结点，用set来维护不同的小组
每次得到一对新的字符串，遍历set中每条链表的每个结点
只要其中一个字符串已经存在于某结点：
        继续遍历该链表，如果另一个结点也存在其中，则完成
        如果另一个字符串不在相同链表中，则继续遍历剩下的链表：
            如果在剩下的链表中找到该字符串，则将这条链表移动到第一条链表后面，并删除原来的链表
            如果找不到，则直接将另一个字符串添加到第一条链表后面。
如果两个字符串都不在所有链表中，则新建两个节点，加入set中。
最后set的size就是小组的数量。
*/
struct ListNode{
    string name;
    ListNode* next;
    ListNode* pre;
};
ListNode* nullptr = new ListNode();//可以注释掉，我的编译器不支持c++11
int main()
{
    int N;
    cin>>N;
    string a,b;
    set<ListNode*> record;
    for(int i=0;i<N;i++){
        cin>>a;
        cin.get();
        cin>>b;
        cin.get();
        //cout<<a<<" "<<b<<endl;
        set<ListNode*>::iterator itor;
        int done_flag=-1;//-1表示未完成, 1表示已经完成
        for(itor = record.begin();itor!=record.end() && done_flag==-1 ;itor++){
            ListNode* node = *itor;
            ListNode* tail = nullptr;//记录第一条链表的尾部
            while(node != nullptr && done_flag!=1 ){
                if(node->name==a || node->name==b){//找到其中一个字符串
                        if(node->name == b && done_flag==-1) swap(a,b);//使b为剩下的字符串
                        //这条路径下是否有b节点
                        while(node != nullptr){
                            if(node ->name == b) {
                                done_flag=1;
                                break;
                            }
                            if(node->next == nullptr) tail = node;
                            node = node->next;
                        }
                        if(done_flag==1) break;
                        //这条路径下没有b节点
                        for(itor++; itor!=record.end() && done_flag!= 1;itor++){//继续遍历剩下的链表
                            ListNode* tmp_node = *itor;
                            ListNode* tmp_head = *itor;
                            while(tmp_node != nullptr){
                                if(tmp_node->name == b){//找到了b字符串
                                    tail -> next = tmp_head;
                                    tmp_head->pre = tail;
                                    record.erase(tmp_head);
                                    done_flag = 1;
                                    break;
                                }
                                tmp_node = tmp_node->next;
                            }
                        }
                        if(done_flag != 1){//没有找到b字符串，新建节点添加到a所在链表的尾部
                            ListNode* n = new ListNode();
                            tail->next= n;
                            n->name = b;
                            n->pre = tail;
                            n->next = nullptr;
                            done_flag = 1;
                        }
                }
                node = node->next;
            }
        }
        if(itor == record.end() && (done_flag==-1)){
            ListNode* n1 = new ListNode();
            ListNode* n2 = new ListNode();
            n1->name = a;
            n2->name = b;
            n1->next = n2;
            n1->pre = nullptr;
            n2->pre = n1;
            n2->next = nullptr;
            record.insert(n1);
        }
    }

    cout<<record.size()<<endl;

    return 0;
}