Strongly connected HDU - 4635
思路：
code： 莫名bug，找了一天心累了，懒得找了
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e5 + 5; struct node{ int u, v, next; }g[maxn]; int head[maxn]; int dfn[maxn], low[maxn], stack[maxn], cot, cnt, opt, sum; bool vis[maxn]; int index[maxn], in[maxn], out[maxn], totol[maxn]; void add(int u, int v){ g[++cnt].u = u; g[cnt].v = v; g[cnt].next = head[u]; head[u] = cnt; } void init(int n){ cot = cnt = opt = sum = 0; for(int i = 1; i <= n; i++){ dfn[i] = low[i] = 0; vis[i] = false; head[i] = 0; index[i] = 0; in[i] = out[i] = totol[i] = 0; } } void targan(int u) { dfn[u] = low[u] = ++cot; stack[opt++] = u; vis[u] = true; for(int i = head[u]; i != 0; i = g[i].next){ int v = g[i].v; if(!dfn[v]) { targan(v); low[u] = min(low[u], low[v]); } else if(vis[i]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]){ int res; sum++; do{ res = stack[--opt]; vis[res] = false; index[res] = sum; totol[sum]++; //记录强联通分量的节点数 } while(res != u); } } int main(){ int t, n, m, u, v; int ans; scanf("%d", &t); for(int ca = 1; ca <= t; ca++){ scanf("%d%d", &n, &m); init(n); for(int i = 0; i < m; i++){ scanf("%d%d", &u, &v); add(u, v); } for(int i = 1; i <= n; i++) if(!dfn[i]) targan(i); for(int i = 1; i <= cnt; i++) { int pre = g[i].u; int cur = g[i].v; if(index[pre] == index[cur]) continue; out[index[pre]]++; in[index[cur]]++; } int mix = 1e9; for(int i = 1; i <= sum; i++) if(!in[i] || !out[i]) mix = min(mix, totol[i]); long long ans; if(sum == 1) ans = -1; else ans = (long long)n * (n - 1) - (long long)m - (long long)mix * (n - mix); printf("Case %d: %lld\n", ca, ans); } }dalao code：
#include <cstdio> #include <cstring> #include <algorithm> typedef long long ll; using namespace std; const int N = 1e5 + 5, M = 1e5 + 5; struct E { int v, next;} e[M]; int t, n, m, u, v, len, h[N], minv, scc_cnt, top, num, id[N], scc[N], ind[N], outd[N], dfn[N], low[N], stack[N]; bool in_st[N]; void add(int u, int v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;} void tarjan(int u) { dfn[u] = low[u] = ++num; stack[++top] = u; in_st[u] = true; for (int j = h[u]; j ; j = e[j].next) { int v = e[j].v; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (in_st[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { int v; scc_cnt++; do { v = stack[top--]; in_st[v] = false; id[v] = scc_cnt; scc[scc_cnt]++; } while (u != v); } } int main() { scanf("%d", &t); int cas = 1; while (t--) { memset(h, 0, sizeof(h)); len = num = top = scc_cnt = 0; minv = 1e9; memset(in_st, false, sizeof(in_st)); memset(dfn, 0, sizeof(dfn)); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); memset(id, 0, sizeof(id)); memset(scc, 0, sizeof(scc)); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); add(u, v); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int u = 1; u <= n; u++) { for (int j = h[u]; j; j = e[j].next) { int v = e[j].v; if (id[v] == id[u]) continue; ind[id[v]]++, outd[id[u]]++; } } //求出度为0 或者 入度为0的SCC的最少点数 for (int i = 1; i <= scc_cnt; i++) { if (!ind[i] || !outd[i]) minv = min(minv, scc[i]); } if (scc_cnt == 1) printf("Case %d: -1\n", cas++); else printf("Case %d: %lld\n", cas++, (ll)n * (n - 1) - (ll)m - (ll)minv * (n - minv)); } return 0; }