這道題應該也是經典的SCC題了吧

印象中不知道在在班里上課的時候在紫書，ACM競賽的那些書上看到多少次（有點奇怪）

首先思路很明顯，就是要找出有多少個點，以它們為起點可以遍歷整個圖

首先考慮一種情況，這種情況是多數SCC題目的突破口，即：環對題目的影響

我們發現，對于這道題，我們如果把環縮點，那么還是一樣的

因為一個環中所有點都可以互相到達，因此縮點后每一個點內部相當于都可以直接到達，我們只需要統計一下每一個SCC中有多少個點然后就等價了

這里有一個結論，還是挺有用的：

在有向圖中，如果有且僅有一個點的出度為0 （沒有指向其他點的邊），那么該點可以被所有點遍歷到；反之，該圖中沒有可以被所有點遍歷到的點

證明（都沒有dalao給出證明，那我還是證一下好了）：用反證法

假設有多個點的出度為0，我們設其中一個點為x，另一個點為y

因為它們的出度為0，那么我們知道x，y之間必然沒有邊

那么x必然無法遍歷到y，因為x，y出度均為0，所以x也無法通過間接關系遍歷到y

假設不成立，原命題得證。

然后就按上面的想法看一下出度為0的點是否唯一即可

CODE

#include<cstdio> #include<cstring> using namespace std; const int N=10005; struct edge {int to,next; }e[N*5]; int head[N],dfn[N],low[N],stack[N],col[N],t[N],chu[N],n,m,x,y,cnt,tot,top,sum,ans=-1; bool vis[N]; inline char tc(void) {static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } inline void read(int &x) {x=0; char ch=tc();while (ch<'0'||ch>'9') ch=tc();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); } inline void add(int x,int y) {e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt; } inline int min(int a,int b) {return a<b?a:b; } inline void Tarjan(int now) {dfn[now]=low[now]=++tot;stack[++top]=now; vis[now]=1;for (register int i=head[now];i!=-1;i=e[i].next)if (!dfn[e[i].to]){Tarjan(e[i].to);low[now]=min(low[now],low[e[i].to]);} else if (vis[e[i].to]) low[now]=min(low[now],dfn[e[i].to]);if (dfn[now]==low[now]){t[++sum]+=1; vis[now]=0;col[now]=sum;while (stack[top]!=now){t[sum]+=1; vis[stack[top]]=0;col[stack[top--]]=sum;} --top;} } int main() {//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);register int i,j;memset(head,-1,sizeof(head));memset(e,-1,sizeof(e));read(n); read(m);for (i=1;i<=m;++i)read(x),read(y),add(x,y);for (i=1;i<=n;++i)if (!dfn[i]) Tarjan(i);for (i=1;i<=n;++i)for (j=head[i];j!=-1;j=e[j].next)if (col[i]!=col[e[j].to]) ++chu[col[i]];for (i=1;i<=sum;++i)if (!chu[i]){if (ans!=-1) { puts("0"); return 0; }ans=t[i];}printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/cjjsb/p/9037948.html

總結

以上是生活随笔為你收集整理的Luogu P2341 [HAOI2006]受欢迎的牛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。