首页 > 代码库 > UVA 10510 - Cactus(有向仙人掌图判定)
UVA 10510 - Cactus(有向仙人掌图判定)
UVA 10510 - Cactus
题目链接
题意:给定一个有向图,问这个图是否为仙人掌图(一条边不属于两个及以上环)
思路:类似构造scc的dfs,判定方法为:
1、必然是一个强连通分量
2、一个环上的节点必然只能经过一次
那么dfs的时候,只要记录下每个结点的父亲结点,如果遇到一个结点之前遍历过了,那么就回退的找到改结点,把环上的结点都+1(注意当前结点不算,因为多个环可以连在一个结点上),然后如果有一个结点超过了2,就肯定不是仙人掌图了
代码:
#include <cstdio> #include <cstring> #include <vector> #include <stack> #include <algorithm> using namespace std; const int N = 20005; vector<int> g[N]; int pre[N], lowlink[N], fa[N], dfs_clock, scc_cnt, cnt[N]; int flag; bool find(int v, int u) { while (fa[u] != v) { cnt[u]++; if (cnt[u] > 1) return false; u = fa[u]; } return true; } bool dfs_scc(int u) { pre[u] = lowlink[u] = ++dfs_clock; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { fa[v] = u; if (!dfs_scc(v)) return false; lowlink[u] = min(lowlink[u], lowlink[v]); } else { lowlink[u] = min(lowlink[u], pre[v]); if (!find(v, u)) return false; } } if (lowlink[u] == pre[u]) { scc_cnt++; if (scc_cnt == 2) return false; } return true; } bool find_scc(int n) { dfs_clock = scc_cnt = 0; memset(cnt, 0, sizeof(cnt)); memset(pre, 0, sizeof(pre)); for (int i = 0; i < n; i++) { if (!pre[i] && !dfs_scc(i)) return false; } return true; } int T, n, m; int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) g[i].clear(); int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); } printf("%s\n", find_scc(n) ? "YES" : "NO"); } return 0; }
UVA 10510 - Cactus(有向仙人掌图判定)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。