并查集这部分个人用了C#实现。一开始把题目理解错了，以为完全子图就是一个简单的弱联通图，直到用并查集秒完，等到DLL快交上去才发现原来指的是强连通子图。这里讲一下这里的设计思路。

讯享网

并查集

        并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。在探索各个作者间的合作关系中用到了并查集思想。并查集需要实现三个功能：

初始化:把每个点所在集合初始化为其自身。在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O（1）

查找:查找元素所在的集合，即根节点。

合并:将两个元素所在的集合合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

        因为并查集时基于线性数组实现的，而在DBLP中的节点是一个个string的作者名称。因此需要将每个作者用一个int的离散化编号来表示。

        这里使用了C#中Dictionary<K,T>的数据结构，可以实现键值对的映射，该结构是使用哈希表和采用链接(Chainning)技术解决冲突的字典，即对于每个冲突的哈希值元素，都会被添加到桶（bucket）的链表中，在查询和添加操作时时间复杂度为O(1),有较好的效率，采用了这个实现了数据离散化和String字符串的作者名到一个整数类型的映射。

        最终，并查集算法设计思路为遍历每篇文章，检查该文章下的每一个作者，当读入一个新的作者，若检测到字典中没有该作者对应的编号，则分配一个数据编号给该作者，并与在同一片文章中的其他作者节点合并。

Dictionary<string, int> Discretization = new Dictionary<string, int>(); //作者名字数据离散化 int[] Parallel = new int[]; //300w并查集 for (int i = 0; i < ; i++) //并查集初始化 { Parallel[i] = i; } int titleAua = 0; for (遍历所有文章) { if (如果该行数据是标题) { titleAua = 0; //重置序列号 } else { titleAua++; //记录一次序列号 if (!Discretization.ContainsKey(infile[auI]))//如果该作者没有编号 { Discretization.Add(infile[auI], authorIndex); //分配一个离散化编号 authorIndex++; } if (titleAua > 2) //如果该作者不是该文章中的第一个作者 ParallelNodeMerge(ref Parallel, Discretization[infile[auI]], Discretization[infile[auI - 1]]); //与前一个作者节点合并 } }

        合并并查集时，采用了递归调用并赋值的思想。在查询到最新的节点，也会将结果回溯到前面的节点及时更新数据，这样保证了再次查找时的效率和总体O(1)的复杂度。（这点对优化效率是非常重要的）最后通过遍历并查集，重载了C#的比较函数，将较大的并查集结果写入文件进行保存。测试时280w数据的包括IO+并查集分析+排序时间，最终耗时没有超过1min。

讯享网private static int Findx(ref int[] Parallel, int x) //查找并查集父节点 { if (Parallel[x] != x) return Parallel[x] = Findx(ref Parallel, Parallel[x]); return x; }

重载比较函数对并查集内一个集合的数目进行排序，并写入文件

{ List<int> aua = new List<int>(); //大于100需要统计的聚团编号 Discret.Clear(); List<string> content = new List<string>(); int tot = 0; foreach (var pr in Discretization) { tot++; content.Add(pr.Key + " " + Findx(ref Parallel, Parallel[pr.Value])); if (!Discret.ContainsKey(Parallel[pr.Value])) Discret.Add(Parallel[pr.Value], new List<string>()); Discret[Parallel[pr.Value]].Add(pr.Key); if (Discret[Parallel[pr.Value]].Count == 100) aua.Add(Parallel[pr.Value]); } File.AppendAllLines(Program.filePath + "database\\aua_result.dat", content); Console.WriteLine("作者数大于100的集合数目：" + aua.Count); Console.WriteLine("将排行榜数据写入文件中..." + aua.Count); aua.Sort(new cmp()); File.WriteAllText(Program.filePath + "database\\aua_rank_result.dat", "作者数>100的聚团数目 " + aua.Count + "\n"); if (!Directory.Exists(Program.filePath + "database\\aua_result")) Directory.CreateDirectory(Program.filePath + "database\\aua_result"); foreach (var i in aua) { File.AppendAllText(Program.filePath + "database\\aua_rank_result.dat", i + " " + Discret[i].Count + "\n"); File.WriteAllLines(Program.filePath + "database\\aua_result\\" + i + ".ini", Discret[i]); } } class cmp : IComparer<int> { public int Compare(int x, int y) { return Discret[y].Count - Discret[x].Count; } } private static int GetParallelCount(ref int[] Parallel, int n) //查询并查集中拥有的总集合数 { int ans = 0; for (int i = 0; i < n; i++) { if (i == Findx(ref Parallel, i)) ans++; } return ans; }

完全子图问题

        完全子图问题实际上就是最大团问题，是一个图论中经典NP问题。这里受限于当时项目时间限制没有写完，这里抛一些当时的想法供思考。

        当时我们隔壁组用的是fp-tree（然后内存炸了）在这里讨论用的是类似DP的思想。即当N-1阶完全子图已被确定时，是否讲当前节点 x 放入N阶子图，只需要判断x是否于N-1阶中的子图中全部相连即可。参考和优化可以借鉴其他网上的思路：