algorithm - 如何从具有链接信息的配对数据列表中找到唯一名称的数量？

Question

我有“n”行数据集，每个数据集都有两个由空格分隔的组件。第一个是卡号，第二个是姓名。一个人是同一个人，如果他有相同的卡号或姓名。如何从数据集中找到唯一身份的总数？

例子:

1个

1乙

2乙

3C

这个数据集有 2 个独特的人。这是因为第一行和第二行卡号相同，第二行和第三行名称相同。

什么样的算法可以用来解决这类问题？

Answer 1

这是另一个使用图论和连通分量的解决方案:

              int CountUnique(Person[] persons)
                Dictionary<string, int> phones = new Dictionary<string, int>();
                Dictionary<string, int> emails = new Dictionary<string, int>();
                bool[] unique = new bool[n];
                int count = 0;
                int max = 0;
                for (int i = 0; i < n; i++)
                {
                    Person p = persons[i];
                    int pA = -1, pB = -1;
                    if (phones.ContainsKey(p.Phone))
                    {
                        pA = phones[p.Phone];
                    }
                    if (emails.ContainsKey(p.Email))
                    {
                        pB = emails[p.Email];
                    }
                    if (pA != -1)
                    {
                        persons[pA].Next.Add(p);
                        p.Next.Add(persons[pA]);
                    }
                    else
                    {
                        phones.Add(p.Phone, p.Index);
                    }

                    if (pB != -1 && pB != pA)
                    {
                        persons[pB].Next.Add(p);
                        p.Next.Add(persons[pB]);
                    }
                    if (pB == -1)
                    {
                        emails.Add(p.Email, p.Index);
                    }
                }


                int current = 0;
                Person pCurrent;
                count = 0;
                while ((pCurrent = FindUnvisited(persons, current)) != null)
                {
                    BFS(pCurrent);
                    count++;
                }

                return count;


            }

            private static void DFS(Person pCurrent)
            {
                pCurrent.Visited = true;
                foreach (Person p in pCurrent.Next)
                {
                    if (!p.Visited)
                    {
                        BFS(p);
                    }
                }
            }

            private static Person FindUnvisited(Person[] persons, int current)
            {
                for (int i = current; i < persons.Length; i++)
                {
                    if (persons[i].Visited == false) return persons[i];
                }
                return null;
            }


        }
    }