3 3 3 1 2 2 3 3 1 3 3 1 2 2 3 1 3 6 6 1 2 2 3 3 1 4 5 5 6 6 4
Case 1: -1 Case 2: 1 Case 3: 15
1 #include <bits/stdc++.h> 2 using namespace std; 3 using LL = long long; 4 const int INF = 0x3f3f3f3f; 5 const int maxn = 100010; 6 7 vector<int>g[maxn]; 8 stack<int>stk; 9 int dfn[maxn],low[maxn],belong[maxn],cnt[maxn],clk,scc; 10 int ind[maxn],oud[maxn]; 11 bool instack[maxn]; 12 void tarjan(int u) { 13 dfn[u] = low[u] = ++clk; 14 stk.push(u); 15 instack[u] = true; 16 for(int i = g[u].size()-1; i >= 0; --i) { 17 if(!dfn[g[u][i]]) { 18 tarjan(g[u][i]); 19 low[u] = min(low[u],low[g[u][i]]); 20 } else if(instack[g[u][i]]) 21 low[u] = min(low[u],dfn[g[u][i]]); 22 } 23 if(low[u] == dfn[u]) { 24 int v; 25 do { 26 instack[v = stk.top()] = false; 27 belong[v] = scc; 28 stk.pop(); 29 ++cnt[scc]; 30 } while(v != u); 31 ++scc; 32 } 33 } 34 int main() { 35 int kase,n,m,u,v,cs = 1; 36 scanf("%d",&kase); 37 while(kase--) { 38 scanf("%d%d",&n,&m); 39 for(int i = 0; i <= n; ++i) { 40 g[i].clear(); 41 dfn[i] = cnt[i] = 0; 42 ind[i] = oud[i] = 0; 43 } 44 for(int i = scc = 0; i < m; ++i) { 45 scanf("%d%d",&u,&v); 46 g[u].push_back(v); 47 } 48 for(int i = 1; i <= n; ++i) 49 if(!dfn[i]) tarjan(i); 50 for(int i = 1; i <= n; ++i){ 51 for(int j = g[i].size()-1; j >= 0; --j){ 52 if(belong[i] == belong[g[i][j]]) continue; 53 ++ind[belong[g[i][j]]]; 54 ++oud[belong[i]]; 55 } 56 } 57 int x = INF,y = n; 58 for(int i = 0; i < scc; ++i) 59 if(!ind[i] || !oud[i]) x = min(x,cnt[i]); 60 y -= x; 61 LL ret = (LL)x*(x - 1) + (LL)y*(y - 1) + (LL)x*y - m; 62 printf("Case %d: %I64d\n",cs++,scc == 1?-1LL:ret); 63 } 64 return 0; 65 }
原文：http://www.cnblogs.com/crackpotisback/p/4966236.html
