本文主要是介绍HDU 3639 Hawk-and-Chicken(强连通），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 3639 Hawk-and-Chicken
题目链接
题意：就是在一个有向图上，满足传递关系，比如a->b, b->c，那么c可以得到2的支持，问得到支持最大的是谁，并且输出这些人
思路：先强连通的缩点，然后逆向建图，对于每个出度为0的点，进行dfs求哪些点可达这个点
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <queue>
using namespace std;const int N = 5005;int t, n, m;
int sccn, dfs_clock, sccno[N], pre[N], dfn[N];
stack<int> S;
vector<int> g[N], save[N], scc[N];void dfs_scc(int u) {pre[u] = dfn[u] = ++dfs_clock;S.push(u);for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!pre[v]) {dfs_scc(v);dfn[u] = min(dfn[u], dfn[v]);} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);}if (pre[u] == dfn[u]) {++sccn;save[sccn].clear();while (1) {int x = S.top(); S.pop();sccno[x] = sccn;save[sccn].push_back(x);if (x == u) break;}}
}void find_scc() {dfs_clock = sccn = 0;memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));for (int i = 0; i < n; i++)if (!pre[i]) dfs_scc(i);
}int out[N];
int ans[N], an, dp[N], vis[N];int dfs(int u) {vis[u] = 1;int ans = save[u].size();for (int i = 0; i < scc[u].size(); i++) {int v = scc[u][i];if (vis[v]) continue;ans += dfs(v);}return ans;
}int main() {int cas = 0;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);}find_scc();memset(out, 0, sizeof(out));for (int i = 1; i <= sccn; i++) scc[i].clear();for (int u = 0; u < n; u++) {for (int j = 0; j < g[u].size(); j++) {int v = g[u][j];if (sccno[u] != sccno[v]) {scc[sccno[v]].push_back(sccno[u]);out[sccno[u]]++;}}}int Max = 0;for (int i = 1; i <= sccn; i++)if (!out[i]) { memset(vis, 0, sizeof(vis));dp[i] = dfs(i);Max = max(Max, dp[i]);}an = 0;for (int i = 1; i <= sccn; i++) {if (!out[i] && dp[i] == Max) {for (int j = 0; j < save[i].size(); j++) {ans[an++] = save[i][j];}}}sort(ans, ans + an);printf("Case %d: %d\n", ++cas, Max - 1);for (int i = 0; i < an; i++)printf("%d%c", ans[i], i == an - 1 ? '\n' : ' ');}return 0;
}这篇关于HDU 3639 Hawk-and-Chicken(强连通）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
