C++党 哈希表居然没人用，思路很简单 用并查集91分有一个样例没过

解题思路:话不多说，先上图

其中我们用哈希表的拉链法，h[i]表示i学生，而下拉的链表是她所要教的学生，如果他的学生也有学生，直接将他学生的学生也放入i对应的链表末尾，同时将他学生的val值设置为0（val是他所教的学生的状态，如果自己是老师为2，自己没人教也不带学生则为1，否则就代表学生是有人带的则设置为0，最后遍历哈希表，如果val不是0，则说明他一定是关键元素）

最后访问哈希表，如果val的值为1或2，直接cnt++就OK

注意事项:因为h[i]的学生会存在自己也在里面，所以我们应该不在自己的学生链表里处理自己，否则会死循环（参考解题思路的逻辑）

参考代码:

#include<iostream> 
#include<string.h>
using namespace std;
struct node//定义链表 
{
	int val;
	struct node* next;//指针指向自己教的学生，如果有就指向下一个 
};
const int N=1e6+10;
node* h[N];//哈希表  h[i]代表第i个学生是否教别人，如果是则val为2，不是则为1，但是如果被别人教了设置为0  很关键
node* find_last(node* q) //寻找第i个人的学生的最后一名 方便将被教的人以及被教的学生一起插入到后面 
{
	while(q->next) q=q->next;
	return q;
}
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		node* temp=new node;
 		temp->val=0;
		temp->next=NULL;
		h[i]=temp;
	}//哈希表的初始化，每个里面装的是第i个学生的初始信息，即都是等待被教的 
	for(int i=1;i<=n;i++)
	{
		int temp;
		while(cin>>temp&&temp)//输入的数据为0就停止 
		{
			node *p=new node;//类似链表的头插法，将第i个人的学生插入到他的下面，表示会教下列学生 
			p->next=h[i]->next;
			h[i]->next=p;
			p->val=temp;
		}
		if(h[i]->next)h[i]->val=2;//如果下面是有节点，代表他是老师设置为2 
		else h[i]->val=1;//不然设置为1，代表i学生不教人 
	}//将数据的初始化完毕了 
	for(int i=1;i<=n;i++)//从1到n遍历哈希表，同时遍历i的学生，如果他的学生又有学生，直接将他的学生接到i学生的最后面同时将他的学生的val设置为0，代表已经被教了 
	{
		node* p=new node;
		p=h[i]->next;//指向i的学生 
		while(p)
		{
			if(h[p->val]->val&&p->val!=i) //i的下面有学生 并且不是自己，（如果处理了自己会死循环） 
			{
				node* q=h[p->val]->next;//找到该学生 
				node* r=find_last(p);//找到i的尾巴 
				r->next=q;//将他学生所带的学生一起接在后面
				h[p->val]->val=0;//代表已经被教了 
				h[p->val]->next=NULL;//要将该学生下面的指针设置为空，防止野指针 
			}
			p=p->next;//找到i的下一个学生 
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(h[i]->val) cnt++;//一旦自己不为零，代表自己下面是有学生，或者我没人教，一定是关键元素，那么计数++就OK 
	}
	cout<<cnt;
	return 0;
}