个人无网站怎样做cps广告/百度指数移动版

广度优先遍历：

模板题

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const ll maxn = 1e6 + 5;
//book用来标记哪些点走过了
int idx,h[maxn],e[maxn],nex[maxn],book[maxn];
int n,m,a,b;
//插入函数
void add(int a,int b)
{e[idx] = b;nex[idx] = h[a];h[a] = idx++;
}
int bfs()
{queue<int> qu;//加入节点1qu.push(1);int temp;//标记节点1book[1] = 1;while(qu.size()){//取出第队首节点temp= qu.front();//走到n了就停if(temp == n)break;//扩展下一个节点for(int i = h[temp]; i != 0; i = nex[i]){if(!book[e[i]]){//距离加一book[e[i]] = book[temp] + 1;qu.push(e[i]);}}qu.pop();}return book[n] - 1;
}
int main()
{idx = 1;cin >> n >> m;for(int i = 0; i < m; i++){cin >> a >> b;add(a,b);}cout << bfs() << endl;return 0;
}

拓扑排序：

题目

思路

1.对于序列的第一个节点一定是没有入度的点，因为没有任何边指向它，所以我们可以把所有没有入度的点加入序列的前面。

2.加入之后，我们再想那么下面应该放什么呢，可以发现接下来的点应该是在刚才加入的节点之后，所以他们应该只能被前面的节点所指，那就好办了，我们可以把刚才那些节点所指向点的入度减一，如果减之后入度为零就加入序列。

3.这样的话我们就又确定了一波节点，我们可以再用这些点重复2的操作如此一来拓扑排序就完成了，我们发现这个过程可以使用一个队列来进行，而最终的结果恰巧也就是排好的这个序列(比较不严谨的说法)。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxn = 1e5 + 5;
//e为终点，qu是队列，eg是出度
ll cnt,ne[maxn],endd[maxn],h[maxn],eg[maxn],qu[maxn];
ll a,b,n,m;
void add(ll a, ll b)
{endd[cnt] = b;ne[cnt] = h[a];h[a] = cnt++;
}
int bfs()
{int he = 0,ed = -1,next;//找出无出度的边for(int i = 1; i <= n; i++)if(!eg[i])//加入队列qu[++ed] = i;//bfs扩展while(he <= ed){next = qu[he++];for(int i = h[next]; i != 0; i = ne[i]){//指向的出度减少eg[endd[i]]--;//出度为零加入队列if(!eg[endd[i]])qu[++ed] = endd[i];}}//全部遍历就存在拓扑序返回1if(he == n)return 1;else{cout << ed << endl;return 0;}
}
int main()
{cin >> n >> m;cnt = 1;for(int i = 0; i < m; i++){cin >> a >> b;add(a,b);//记录出度eg[b]++;}if(bfs()){//数组qu模拟队列剩下的就是拓扑序列了for(int i = 0; i < n; i++)cout << qu[i] << " ";cout << endl;}elsecout << -1 << endl;return 0;
}