食物链（关于C++for循环的优化写法与拓扑排序）

介绍个for循环的写法
vector < int > e[100];
for(auto t:e[x])

意义：用t作为标记变量来遍历e[x]这个容器内的全部元素

然后是食物链
这个题给了一个拓扑排序的图，是，但不完全是，因为题目中说了有单独的点
入度：进来的边数
出度：出去的边数

BFS做法

#include 
using namespace std;
const int N=1008611;
int n, m, f[N], rd[N];
vector  e[N];
int BFS()
{
    queue q;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!rd[i]&&e[i].size())
        {
            q.push(i);
            f[i]=1;
        }
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
        if(!e[x].size())
         ans+=f[x];
         for(auto t:e[x])
         {
             f[t]+=f[x];
             rd[t]--;
             if(!rd[t])
                q.push(t);
         }
    }
    return ans;
} 

int main ()
{

	//freopen("in.txt","r",stdin);
	cin>>n>>m;
	for(int i=1, x, y; i<=m; i++)
	{
		cin>>x>>y;
        rd[y]++;
		e[x].push_back(y);
	}
	cout< 
重点：考虑第一次入队，和每一次入队的方式
 
DFS做，，，
 我去，，我写不出来啊
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5433796.html