C++ 拓扑排序算法实现 - 判断有向图是否存在环

#include #include #include

using namespace std;

const int N = 100010; // 用来表示节点数的最大值

int h[N], e[N], ne[N], idx; int d[N]; // 存储每个节点的入度 int n, m; // n表示节点数，m表示边数

void add(int a, int b) // 建立有向图的邻接表 { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }

bool topsort() // 实现拓扑排序 { queue q; for (int i = 1; i <= n; i ++ ) if (!d[i]) // 将所有入度为0的节点入队 q.push(i);

while (q.size())
{
    int t = q.front();
    q.pop();
    for (int i = h[t]; ~i; i = ne[i])
    {
        int j = e[i];
        if (-- d[j] == 0) // 将与当前节点相关联的节点的入度减1
            q.push(j); // 如果减1后该节点的入度为0，则将其入队
    }
}

for (int i = 1; i <= n; i ++ )
    if (d[i]) // 如果还有入度不为0的节点，则说明存在环
        return false;

return true;

}

int main() { //初始化计数器，使用邻接表存储有向图 memset(h, -1, sizeof h); cin >> n >> m;

// 构造有向图
while (m -- )
{
    int a, b;
    cin >> a >> b;
    add(a, b);
    d[b] ++ ;
}

// 判断是否有拓扑序 
if (topsort())
    puts("Yes");
else
    puts("No");

return 0;

}