最近一直在忙项目都没时间好好总结写博客，说起来真实惭愧啊。

下面就把自己最近做的几题好好总结一下，主要记录一些注意点，以防以后遇到再犯。

1076. Forwards on Weibo (30)

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

4
5

这个题目的坑在题意不好理解，尤其是像我这种英语比较拙计的人。最后查了几个单词总算理解了题意，本质上就是做搜索。但是涉及到一个是选择dfs还是bfs的问题。刚开始没多想，感觉差不多，后来就用了dfs。

dfs需要注意的几点：

【1】邻居存储数据结构的选择，这里用了邻接表，比较清楚。

【2】注意不能存在回路的情况，比如说1是4的粉丝，4也是1的粉丝。如果先1后4，那么到4的时候就不应该回去再访问1！也就是不能存在回路。

【3】在不能存在回路的基础上，要考虑一种特殊情况，5-1-4 这时候L==0了，也就是说到了限定的最外层。这时候不能再往下搜索，应该退回到5。但是4的邻居此时没有被搜索过。若5的下一个邻居是4，这时候4也要被访问，因为4的邻居可能存在没被访问过的点。

为了解决环路问题，同时兼顾【3】我们设一个点有3种状态

#define  discover 0
#define  cnted 1
#define  undsicover 2

每次访问一个点若该点为 undsicover，那么置为dsicover并cnt++，如果该点本身是dsicover，那么说明存在回路，不再继续。一个点回退后要置为cnted。避免下次访问被跳过，即【3】的情况。

代码：

// pat-1076.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include"iostream"
#include "vector"
#include "algorithm"
#include "fstream"
using namespace std;
#define  discover 0
#define  cnted 1
#define  undsicover 2
int cnt=0;
class node{
public:
	int id;
	vector<node*> neiber;
	int statues;
	node():neiber(NULL),statues(undsicover),id(-1){}
};

void resetall(node* an,int n)
{
	for (int i=0;i<n+1;i++)
	{
		an[i].statues=undsicover;
	}
	cnt=0;
}

void forward(node* p,int l)
{ 
	if (p->statues==discover||l==0)//避免形成回环
	{
		return;
	}
	if ((p->statues==undsicover))//false
	{
		cnt++;//计数加一
		p->statues=discover;//cnted
	}
	if (p->neiber.empty())//没有邻居不用遍历
	{
		return;
	}
	int len=p->neiber.size();
	for (int i=0;i<len;i++)
	{  
		forward(p->neiber[i],l-1);//dfs
	}
	p->statues=cnted;
}

int main()
{
	fstream fcin;
	fcin.open("C:\\Users\\Administrator\\Desktop\\456.txt");

	int n=0,l=0;
	fcin>>n>>l;
	node *an=new node[n+1];//编号从1-n
	for (int i=1;i<=n;i++)
	{
		an[i].id=i;
	}
	for (int i=1;i<=n;i++)
	{   
		int temp=0,j=0;
		fcin>>temp;
		while(temp--)
		{
			fcin>>j;
			an[j].neiber.push_back(&an[i]);//作为目标的邻居而不是把目标作为自己的邻居
		}
	}
	int k=0,index=0;
	fcin>>k;
	for(int i=0;i<k;i++)
	{
		fcin>>index;
                forward(&an[index],l+1);
		cout<<cnt-1<<endl;
		resetall(an,n);
	}
	return 0;
}

上述算法的逻辑没错，但是最后一个点会超时！！！呵呵，随后又写了一个bfs版本的。

// pat-1076.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include"iostream"
#include "vector"
#include "algorithm"
#include "fstream"
#include "queue"
using namespace std;
#define  discover 0
#define  cnted 1
#define  undsicover 2
int cnt=0;

class node{
public:
	int id;
	vector<node*> neiber;
	int statues;
	node():neiber(NULL),statues(undsicover),id(-1){}
};

void resetall(node* an,int n)
{
	for (int i=0;i<n+1;i++)
	{
		an[i].statues=undsicover;
	}
	cnt=0;

}

void bfs(node* p,int l)
{ 
	queue<vector<node*>> q;
	queue<vector<node*>> qq;
	p->statues=discover;
	q.push(p->neiber);
	while(!q.empty())
	{
		if (qq.empty())
		{
			l--;
			qq=q;
		}
		if (l==0)
		{
			return ;
		}
		vector<node*> v=q.front();
		q.pop();
		qq.pop();
	  
		int len=v.size();
		for (int i=0;i<len;i++)
		{
			if (v[i]->statues==undsicover)
			{
				cnt++;
				v[i]->statues=discover;
				if (!v[i]->neiber.empty()&&l>0)
				{
					q.push(v[i]->neiber);
				}
				
			}
		}
	}
}

int main()
{
	fstream fcin;
	fcin.open("C:\\Users\\Administrator\\Desktop\\456.txt");

	int n=0,l=0;
	fcin>>n>>l;
	node *an=new node[n+1];//编号从1-n
	for (int i=1;i<=n;i++)
	{
		an[i].id=i;
	}
	for (int i=1;i<=n;i++)
	{   
		int temp=0,j=0;
		fcin>>temp;
		while(temp--)
		{
			fcin>>j;
			an[j].neiber.push_back(&an[i]);//作为目标的邻居而不是把目标作为自己的邻居
		}
	}
	int k=0,index=0;
	fcin>>k;
	for(int i=0;i<k;i++)
	{
		fcin>>index;
		bfs(&an[index],l+1);
		cout<<cnt<<endl;
		resetall(an,n);
	}
	return 0;
}

这个是可以ac的，果然递归是个坑啊！但是这里涉及到一个计算bfs深度的问题。在dfs里面这很自然，递归的深度就是目前所处树的深度。但是在用stack实现的bfs算法里面没有可用的量。所以这里用了比较笨的办法，开了两个stack，一个是用来计数的。还好stl重载了运算符=，否则代码会有点啰嗦。

如果大家有什么跟好的想法，欢迎交流！