洛谷 USACO06JAN 牛的舞会

xiaoxiao2021-02-28  34

强连通分量的裸体。

解释一下题意:

如果有两头或者两头以上的奶牛被同一根绳子拴着的时候,那么称这一组牛(集体)是可以转圈(符合题意)的;问有多少个这样的集体。

简单的说就是大小大于等于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; }
转载请注明原文地址: https://www.6miu.com/read-2628225.html

最新回复(0)