本文主要是介绍【图论】判环问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
(未更新完、做到相关题再更新相关部分
文章目录
- 无向图判断有无环并输出环上点
无向图判断有无环并输出环上点
例题: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;
这篇关于【图论】判环问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!