POJ2762-Going from u to v or from v to u?(强连通缩点+DP)
to or from DP 连通
2023-09-27 14:25:12 时间
题意:给出一张有向图。推断图上的随意两个点是否存在一条路可达(单向可达就可以)。
思路:有向图找出强连通分量,然后缩点,由于题目要求随意两点存在可达的路,所以缩点之后的点。要形成一条单链,才干符合可达的要求,在这里用DP求最长路来推断能否形成一条单链。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 2010; const int MAXM = 50010; struct Edge{ int to, next; }edge[MAXM]; int head[MAXN], tot; int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN]; int Index, top; int scc; bool Instack[MAXN]; int num[MAXN]; int n, m; int d[MAXN]; vector<int> g[MAXN]; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for (int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if (!DFN[v]) { Tarjan(v); if (Low[u] > Low[v]) Low[u] = Low[v]; } else if (Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if (Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; } while (v != u); } } void solve() { memset(Low, 0, sizeof(Low)); memset(DFN, 0, sizeof(DFN)); memset(num, 0, sizeof(num)); memset(Stack, 0, sizeof(Stack)); memset(Instack, false, sizeof(Instack)); Index = scc = top = 0; for (int i = 1; i <= n; i++) if (!DFN[i]) Tarjan(i); } int dp(int i) { int& ans = d[i]; if (ans > 0) return ans; ans = 1; for (int j = 0; j < g[i].size(); j++) { int v = g[i][j]; ans = max(ans, dp(v) + 1); } return ans; } int main() { int cas; scanf("%d", &cas); while (cas--) { init(); scanf("%d%d", &n, &m); int u, v; for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); addedge(u, v); } solve(); if (scc == 1) { printf("Yes\n"); continue; } else { for (int i = 0; i <= scc; i++) g[i].clear(); for (int u = 1; u <= n; u++) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (Belong[u] != Belong[v]) g[Belong[u]].push_back(Belong[v]); } } memset(d, -1, sizeof(d)); int ans = 0; for (int i = 1; i <= scc; i++) ans = max(ans, dp(i)); if (ans == scc) printf("Yes\n"); else printf("No\n"); } } return 0; }
相关文章
- Upgrading to Java 8——第四章 The Stream API
- 解决 警告: [SetPropertiesRule]{Server/Service/Engine/Host/Context} Setting property 'source' to 'org.eclipse.jst.jee.server:reyo' did not find a matching property.
- 问题解决:psql: could not connect to server: No such file or directory Is the server running locally and accepting connections on Unix domain socket "/var/run/postgresql/.s.PGSQL.5432"?
- [Kaggle] How to handle big data?
- AI、区块链引爆企业级市场,硅谷Wisemont分享To B项目投资经验
- Azure 入门系列 (第三篇 Publish Web Application to VM)
- valgrind: failed to start tool 'memcheck' for platform 'amd64-linux': No such file or directory
- Plugin org.apache.maven.plugins:maven-clean-plugin:2.4.1 or one of its dependencies could not be resolved: Failed to read artifact descriptor for org.apache.maven.plugins:maven-clean-plugin:jar:2.4.1
- Plugin is too old, please update to a more recent version, or set ANDROID_DAILY_OVERRIDE environment
- If you want to allow applications containing errors to be published on the server
- SGU 275. To xor or not to xor (高斯消元法)
- 1092 To Buy or Not to Buy (20 分)
- How to use --extra-index-url in requirements.txt in python?
- 【LeetCode从零单排】No121Best Time to Buy and Sell Stock
- How To Move Or Rebuild A Lob Partition
- You need to use a Theme.AppCompat theme (or descendant) with this activity.
- FreeBSD下的Apache出现错误:[warn] (2)No such file or directory: Failed to enable the 'httpready' Accept Filter的解决方法
- 安装Visual Studio 2010时提示"The location specified for the help content store is invalid or you do not have access to it".
- How To Setup A Linux Active Defense System Or Intrusion Detection System On Linux
- Communications link failure due to underlying exception异常处理(转)
- Android AdbCommandRejectedException和cannot bind to套接字地址(协议/网络地址/端口)只允许使用一次
- 【我的Android进阶之旅】解决bug:You need to use a Theme.AppCompat theme (or descendant) with this activity.