计科陈冠希


私信TA

用户名:uq_80401439734

访问量:200

签 名:

自我感觉很帅

等  级
排  名 160
经  验 6142
参赛次数 10
文章发表 4
年  龄 8
在职情况 学生
学  校 西北师范大学
专  业 计算机科学与技术

  自我简介:

雅虎~!

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

DB468EEF4FE93CE6816E90D3090B4BA0.jpg

其中我们用哈希表的拉链法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;
}


 

0.0分

1 人评分

  评论区