强连通分量的裸体。
解释一下题意:
如果有两头或者两头以上的奶牛被同一根绳子拴着的时候,那么称这一组牛(集体)是可以转圈(符合题意)的;问有多少个这样的集体。
简单的说就是大小大于等于2的强连通分量的个数有多少个。
不就是裸体吗?
代码:
#include<bits/stdc++.h> using namespace std; const int N=10000+5; vector<int> olg[N]; stack<int> s; int seq,num,n,m,a,b,tmp1,tmp2,ans; int dfn[N],low[N],ind[N]; bool ins[N]; void tarjan(int x){ int j; dfn[x]=low[x]=++seq; s.push(x);ins[x]=true; for(int i=0;i<olg[x].size();i++){ j=olg[x][i]; if(!dfn[j]){ tarjan(j); low[x]=min(low[x],low[j]); } else if(ins[j]) low[x]=min(low[x],dfn[j]); } if(dfn[x]==low[x]){ num=0; while(s.top()!=x){ num++; ins[s.top()]=false; s.pop(); } num++; ins[x]=false; s.pop(); if(num>1) ans++; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); olg[a].push_back(b); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); cout<<ans; return 0; }