题目大意
一个有向图，有$n$个节点$m$条边，输入$n$和$m$和每条边的起点和终点。
判断有向图的所有点是否都能在拓扑序中。能就输出Valid，否则输出Invalid。
题解
看到原题有
其中的第$i$条约束要求在学习第$y_i$ 门课程之前，必须先修完第$x_i$门课程。
这样的优雅表述，判断可以用拓扑排序来解。
拓扑排序是通过按照某个拓扑序的方法来遍历一张有向图。举个例子：
这是一张有5个结点的有向图。遵循的原则是：
当某个点的所有前驱节点都已被遍历时，这个点就可以被遍历。
（可能不是前驱，但意思等同于前驱）
例如，这张图中，1没有前驱节点。可以先遍历1，随后3没有别的前驱了，需要遍历3。此时点2的所有前驱都被遍历，可以遍历点2。此时4的所有前驱都被遍历，可以遍历点4。此时，5的前驱即3和4都被遍历，可以遍历5。本图的一种拓扑序即为1 3 2 4 5。
一张图可能有多个拓扑序。例如将本图中1到3的边删掉，就可以有1 3 2 4 5和3 1 2 4 5两个拓扑序。
回到本题。题目说的矛盾即为存在一个点无法被拓扑序遍历到。
例如样例1的图，简单画一下就可以发现它没有任何一个节点是没有前驱节点的，拓扑序无从建起，自然是Invalid。
那么推广一下，思路出来了：
为图进行一次按照拓扑序的遍历，看看是否能够遍历到每一个点。如果不能遍历到每一个点，就是存在矛盾，输出Invalid。否则Valid。
实现
用一个邻接表来存储有向图。
const int MAXN=200005;
vector<int> v[MAXN];
首先输入$n$,$m$的值，并建图。
注意到，判断一个点是否有前驱，可以通过存储其入度的数量来简单判断。如果它的入度数量为0，那么它没有前驱。所以定义一个数组来存储某个点的入度数量。
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
d[b]++;//存入度数量的数组 int类型
}
看到刚才举的例子，当点1被遍历后，它下一个点可以选择遍历点2或者点3。但是点2还有别的前驱，点3没有了。所以遍历点3。
那么这样，就可以通过bfs，将遍历到的点指向的点的入度都减去1，即”消去一条边“。当指向的点入度变成0的时候，入队，对它bfs。
for(int i=1;i<=n;i++)if(!d[i])q.push(i);//初始化 找拓扑序起点
while(!q.empty())
{
int x=q.front();q.pop();//bfs
cnt++;//记录遍历了多少个点
for(int i=0;i<v[x].size();i++)
{
int final=v[x][i];
d[final]--;//消边
if(!d[final])q.push(final);//如果指向的点没有别的前驱了就入队
}
}
按照思路，我们统计一下遍历了多少个点，如果$cnt==n$，那么Valid。否则Invalid。
cout<<((cnt!=n)?"Invalid":"Valid");
AC Code
//20231106 @ iai.sh.cn
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=200005;
int n,m,d[MAXN],cnt;
vector<int> v[MAXN];
queue<int> q;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("1.txt","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
d[b]++;
}
for(int i=1;i<=n;i++)if(!d[i])q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
cnt++;
for(int i=0;i<v[x].size();i++)
{
int final=v[x][i];
d[final]--;
if(!d[final])q.push(final);
}
}
cout<<((cnt!=n)?"Invalid":"Valid");
return 0;
}