思路:
拓扑排序流程(bfs):
1. 遍历所有点找到入度为0的点,把它们入队
2. 开始从入度为0的点找:
1. 队头出队
2. 遍历队头的临边
3. 临边的度 - 1
4. 判断此时度是否为0:为0说明它可以做新的起点,入队
return tt == n - 1
(队尾下标是n-1,说明所有点都已经入队)
Note
模拟队列的好处就是,只是移动队头队尾指针,实际上拓扑序还在队列中,所以输出时直接遍历就好。
模拟队列
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (d[i] == 0) // 等同于 if (!d[i])
q[ ++ tt ] = i;
while(hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i]; // 找到出边!
d[j] -- ;
if (d[j] == 0)
{
q[ ++ tt] = j;
}
}
}
return tt == n - 1;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++ ;
}
if (!topsort()) puts("-1");
else
{
for (int i = 0; i < n; i ++ )
cout << q[i] << ' ';
}
return 0;
}
stl queue
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int tmp[N];
queue<int> q;
int pos = 0;
bool topsort()
{
//int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (d[i] == 0) // 等同于 if (!d[i])
q.push(i); // q[ ++ tt ] = i;
while(q.size()) // while(hh <= tt)
{
int t = q.front(); //int t = q[hh ++ ];
tmp[pos ++ ] = t;
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i]; // 找到出边!
d[j] -- ;
if (d[j] == 0)
{
q.push(j);// q[ ++ tt] = j;
}
}
}
if (pos == n) return true;
else return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++ ;
}
if (!topsort()) puts("-1");
else
{
for (int i = 0; i < pos; i ++ )
{
cout << tmp[i] << ' ';
}
}
return 0;
}
写queue时老是逻辑有点问题,最后用了y总的printf方法debug,真好用啊!printf大法好!!笔芯yxc