【图论】判环问题

本文主要是介绍【图论】判环问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（未更新完、做到相关题再更新相关部分

无向图判断有无环并输出环上点

例题：H. Mad City

利用变种拓扑排序，先把度为1的点存入队中，每次取出队头，遍历邻接点，再将该条边删除也就是将邻接点度数减一，直至对空，然后所有度数不为0的点都是在环上的点，输出即可

code

for (int i = 0; i < n; i ++ )
{int x, y;cin >> x >> y;add(x, y), add(y, x);ind[x] ++, ind[y] ++ ;
}function<void()> topsort = [&]()
{queue<int> q;for (int i = 1; i <= n; i ++ )if (ind[i] == 1) q.push(i);while (q.size()){int u = q.front();q.pop();for (int i = h[u]; ~i; i = ne[i]){int v = e[i];if (-- ind[v] == 1) q.push(v);}}
};topsort();for (int i = 1; i <= n; i ++ )if (ind[i] > 1) ans = true;

这篇关于【图论】判环问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---