[BZOJ 1051]受欢迎的牛
Tarjan缩点第一题……
很容易想到找出度为0的点（当且仅当这样的点有一个时有解），但是在有环图上这个方法会失效。
处理方法是，用Tarjan的强联通分量算法求出所有SCC，然后把每个SCC缩成一个点，然后再在缩点之后的图上求解即可（这个图是DAG。原因很简单，要是有环还能接着缩）。
代码：
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 | /************************************************************** Problem: 1051 User: danihao123 Language: C++ Result: Accepted Time:72 ms Memory:1692 kb****************************************************************/ #include <cstdio>#include <stack>#include <algorithm>using namespace std;const int maxn=10005,maxm=50005;int first[maxn];int next[maxm],to[maxm];int graph_cnt=0;inline void AddEdge(int u,int v){ graph_cnt++; next[graph_cnt]=first[u]; first[u]=graph_cnt; to[graph_cnt]=v;} int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];stack<int> S;int dfs_clk=0,scc_cnt=0;void dfs(int x){ dfs_clk++; pre[x]=low[x]=dfs_clk; S.push(x); int i,u; for(i=first[x];i;i=next[i]){ u=to[i]; if(!pre[u]){ dfs(u); low[x]=min(low[x],low[u]); }else{ if(!sccno[u]) low[x]=min(low[x],pre[u]); } } if(low[x]==pre[x]){ scc_cnt++; sccsiz[scc_cnt]=0; while(true){ u=S.top(); S.pop(); sccno[u]=scc_cnt; sccsiz[scc_cnt]++; if(u==x) break; } }}int n;inline void Tarjan(){ register int i; for(i=1;i<=n;i++) if(!pre[i]) dfs(i);} bool Out[maxn];int main(){ int m,u,v; register int i,j,ans=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d",&u,&v); AddEdge(u,v); } Tarjan(); for(i=1;i<=n;i++){ for(j=first[i];j;j=next[j]){ u=to[j]; if(sccno[i]!=sccno[u]) Out[sccno[i]]=true; } } for(i=1;i<=scc_cnt;i++){ if(!Out[i]){ if(ans){ ans=0; break; } ans=sccsiz[i]; } } if(n==1) ans=0; printf("%d\n",ans); return 0;} |
