C++ 图论之拓扑排序
应用:
附C++代码:
//
// 1448.cpp
// Legal or Not
//
// Created by chenmeiqi on 2019/4/10.
// Copyright © 2019年 chenmeiqi. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
#define N 100
int main(int argc, const char * argv[]) {
int n,m;
int a,b;
vector<int> edge[N];
while(cin>>n>>m){
if(n==0){
break;
}
for(size_t i = 0; i < N; i++) // 清空邻接链表
{
edge[i].clear();
}
while(m--){
cin>>a>>b;
edge[b].push_back(a); // 这里是保存每个点的入结点
}
int now=-1;
for(int k = now+1; k < N; k++)
{
if(edge[k].size()==0){
if(k==N-1){ // 到了最后一个
cout<<"YES"<<endl;
break;
}
else{ // 更新现在的入度为0的结点
now=k;
}
}
else{ // 还没到最后一个就找不到入度为0的结点了,说明存在环路
cout<<"NO"<<endl;
break;
}
for(int i = 0; i < N; i++) // 去掉当前入度为0的结点的所有边
{
for(int j = 0; j < edge[i].size(); j++)
{
if(edge[i][j]==now){
edge[i].erase(edge[i].begin()+j); // erase(index) 删除vector中某元素
}
}
}
}
}
return 0;
}
这里我略微改造了邻接矩阵,在找入度为0的结点时比较容易,只需判断其vector的size是否为0即可,但是在接下来去掉当前入度为0的结点的所有边时就需要两个for循环才行了。
读者也可正常地构造邻接矩阵,再构造一个数组保存每个结点的入度即可。
另外,在找入度为0的结点时,可以利用queue的特性,一次遍历,依次入队,再一个个取出,直到queue.empty()==true即可。
附queue的相关操作:
queue<int> Q;
Q.push(x); // 将元素放入队尾
x=Q.front(); // 读取队头元素,将其值赋给x
Q.pop(); // 队头元素弹出
Q.empty() // 判断队列是否为空,若返回值为true代表队列为空