1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
| #include <bits/stdc++.h>
using namespace std;
const int MAX = 5000 + 10;
int T, n, m, Case;
vector<int> G1[MAX], G2[MAX];
int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt; stack<int> S;
int self_supports[MAX], dp[MAX], in[MAX]; bool winner[MAX];
void tarjan(int u) { pre[u] = low[u] = ++dfs_clock; S.push(u); for (int i = 0; i < G1[u].size(); i++) { int v = G1[u][i]; if (!pre[v]) { tarjan(v); low[u] = min(low[u], low[v]); } if (!mark[v]) { low[u] = min(low[u], pre[v]); } } if (low[u] == pre[u]) { scc_cnt++; int x; do { x = S.top(); S.pop(); mark[x] = scc_cnt; } while (x != u); } }
void get_G() { for (int i = 1; i <= n; i++) { self_supports[mark[i]]++; } for (int u = 1; u <= n; u++) { for (int i = 0; i < G1[u].size(); i++) { int v = G1[u][i]; if (mark[u] != mark[v]) { G2[mark[u]].push_back(mark[v]); in[mark[v]]++; } } } }
void init() { scanf("%d %d", &n, &m); dfs_clock = scc_cnt = 0; memset(pre, 0, sizeof(pre)); memset(mark, 0, sizeof(mark)); memset(winner, 0, sizeof(winner)); memset(dp, -1, sizeof(dp)); memset(in, 0, sizeof(in)); memset(self_supports, 0, sizeof(self_supports)); for (int i = 0; i <= n; i++) { G1[i].clear(); G2[i].clear(); } for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); u++, v++; G1[v].push_back(u); } }
int dfs(int u) { int ans = self_supports[u] - 1; pre[u] = 1; for (int i = 0; i < G2[u].size(); i++) { int v = G2[u][i]; if (!pre[v]) { ans += dfs(v) + 1; } } return ans; }
void solve() { for (int i = 1; i <= n; i++) { if (!pre[i]) tarjan(i); } get_G(); int ans = 0; for (int i = 1; i <= scc_cnt; i++) { if (in[i] != 0) continue; memset(pre, 0, sizeof(pre)); dp[i] = dfs(i); ans = max(dp[i], ans); } for (int i = 1; i <= scc_cnt; i++) { if (dp[i] == ans) winner[i] = true; } bool fir = true; printf("Case %d: %d\n", ++Case, ans); for (int i = 1; i <= n; i++) { if (winner[mark[i]]) { if (!fir) putchar(' '); printf("%d", i - 1); fir = false; } } putchar('\n'); }
int main() { scanf("%d", &T); while (T--) { init(); solve(); } }
|