一个知识点太久不用就得忘-------------------------------
首先：拓扑排序肯定是运用于有向图的
A:拓扑排序作用：拓扑排序的目标是找到一种节点的线性排列，使得图中的每条有向边的终点在排序中都出现在起点之后，就像执行任务，要先完成该任务所依赖的任务才能完成该任务。
B. DAG（有向无环图）的特点
拓扑排序通常应用于DAG，即有向无环图。DAG具有一个重要特点，即图中不存在从某个节点出发经过若干条有向边回到该节点的闭环。这种特性确保了图中不存在循环依赖，使得任务或事件可以被合理地排序。
在实际应用中，DAG的无环性质使得拓扑排序成为一个有效且可行的算法。当图中存在环路时，无法确定合理的排序顺序，因为存在循环依赖关系。
拓扑排序基本思想：将有向图中的节点按照依赖关系进行线性排序，使得每个节点都在排序中位于其依赖节点之后。这样的排序结果既能满足依赖关系，又能保证整个图中没有环路存在。
为了实现这一目标，拓扑排序算法通过深度优先搜索（DFS）、广度优先搜索（BFS）或Kahn（卡恩）算法等方式遍历图中的节点，并在遍历过程中确定节点的排序顺序。整个算法过程关注的核心是找到一种排列方式，使得图中的所有有向边的终点在排序中都出现在起点之后。
C：卡恩算法：
Kahn算法是一种基于入度的贪心算法。它的工作原理如下：
初始化一个队列，将所有入度为零的节点加入队列。
从队列中取出节点，并在排序结果中加入该节点。
将该节点指向的节点的入度减一，如果某个节点入度变为零，则将其加入队列。
重复上述步骤，直到队列为空。
Kahn算法通过不断减小节点的入度，确保了排序结果中每个节点的入度都为零，符合拓扑排序的要求。它的实现简单高效，适用于大多数DAG。
理解了这些算法原理，我们将能够更深入地思考和实践拓扑排序的具体实现和应用。下一步将着重介绍算法的具体实现方式及其在不同场景中的适用性。
一道cf原题：板子
//F - Chat Screenshots
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int tt;cin>>tt;
{
while(tt--)
{
//读入
int k;
int n;//节点个数
cin>>n>>k;//d为入读数
vector<int> v[n+1],a(n+1),d(n+1);//vector存图，方便找到相邻节点
int cur=0;//数组光标和答案数组
for (int i = 1; i <= k; i++)
{
//x要在y之前完成，就要连一条从x到y的边
for(int j=1;j<=n;j++) cin>>a[j];
for(int j=2;j<=n-1;j++)
{
d[a[j+1]]++;
v[a[j]].push_back(a[j+1]);
}
}
queue<int> q;//入读为0的队列
for (int i = 1; i <= n; i++)//将入度为0的节点加入队列
if (d[i] == 0)
q.push(i);
while (!q.empty())
{
int f = q.front();//取队头结点
++cur;
q.pop();//别忘了把队头出队
for (int i = 0; i < v[f].size(); i++)//遍历与队头相邻的节点
{
int t = v[f][i];//与队头相邻的节点的编号
d[t]--;//入度-1
if (d[t] == 0)//入度为0就入队
q.push(t);
}
}
if (cur != n) //正常情况下应该有n个节点
cout<<"NO"<<'\n';
else
{
cout<<"YES"<<'\n';
}
}
}
}
洛谷模板：
//B3644 【模板】拓扑排序 / 家谱树
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 200005;
#define inf 1<<25
#define YES cout<<"YES"<<'\n';
#define NO cout<<"NO"<<'\n';
void solve()
{
ll n;cin>>n;
vector<ll>d(n+1),a[n+1],ans(n+1),s(n+2);//入度，存边，顺序
for(ll i=1;i<=n;i++)
{
s[0]=i;
for(ll j=1;j<=n+1;j++)
{
cin>>s[j];
if(s[j]==0) break;
}
for(ll j=0;j<=n+1;j++)
{
if(s[j]==0||s[j+1]==0) break;
d[s[j+1]]++;
a[s[j]].push_back(s[j+1]);
}
}
queue<ll>q;
for(ll i=1;i<=n;i++)
{
if(!d[i]) q.push(i);
}
ll e=0;
while(q.size())
{
ll x=q.front();
q.pop();
ans[++e]=x;
for(ll i=0;i<a[x].size();i++)
{
d[a[x][i]]--;
if(d[a[x][i]]==0)
{
q.push(a[x][i]);
}
}
}
for(ll i=1;i<=n;i++) cout<<ans[i]<<' ';
}
int main()
{
ll t;cin>>t;
while(t--)
solve();
return 0;
}
