一道极其水的拓扑排序……但是我还是要把它发出来，原因很简单，连错12次……
题意也很裸，前面的废话不用看，直接看输入
输入n, m表示从0到n-1共n个人，有m组关系
截下来m组，每组输入a, b表示a指向b，或者b指向a也行。
输入n == 0时结束
如果可以拓扑排序，输出"YES",否则输出"NO"。每组输出占一行。
给两种代码吧，一种用邻接矩阵，另一种我也不知道叫什么好……
邻接矩阵——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; const int N = ; int mp[N][N];
int n, m;
int a, b;
int dg[N]; int main()
{
//freopen("test.txt", "r", stdin);
while(~scanf("%d%d", &n, &m) && n)
{
memset(dg, , sizeof(dg));
memset(mp, , sizeof(mp));
for(int i = ; i < m; i++)
{
scanf("%d%d", &a, &b);
if(mp[a][b] == && a != b)
{
dg[b]++;
mp[a][b] = ;
}
} queue<int> que;
for(int i = ; i < n; i++)
{
if(!dg[i]) que.push(i);
} int sum = ;
while(!que.empty())
{
int p = que.front();
que.pop();
sum++;
dg[p]--;
for(int i = ; i < n; i++)
{
if(mp[p][i])
{
dg[i]--;
if(!dg[i])
{
que.push(i);
}
} }
}
if(sum == n) printf("YES\n");
else printf("NO\n"); }
return ;
}
不知名——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; const int N = ; struct Node
{
int to;
int next;
}node[N]; int head[N];
int dg[N];
int n, m;
int a, b; int main()
{
//freopen("test.txt", "r", stdin);
while(~scanf("%d%d", &n, &m) && n)
{
memset(head, -, sizeof(head));
memset(dg, , sizeof(dg));
for(int i = ; i < m; i++)
{
scanf("%d%d", &a, &b);
node[i].to = b;
node[i].next = head[a];
head[a] = i;
dg[b]++;
} int sum = ;
queue<int>que;
for(int i = ; i < n; i++)
{
if(!dg[i])
{
que.push(i);
}
} while(!que.empty())
{
int p = que.front();
que.pop();
dg[p]--;
sum++;
for(int i = head[p]; i != -; i = node[i].next)
{
int v = node[i].to;
dg[v]--;
if(!dg[v])
{
que.push(v);
}
}
}
if(sum == n) printf("YES\n");
else printf("NO\n");
}
return ;
}
知道名字了，叫前向星标……