USACO 06JAN 牛的舞會 洛谷2863

題目描述

The N (2 <= N <= 10,000) cows are so excited: it’s prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.

Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.

They then acquire a total of M (2 <= M <= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed.

約翰的N (2 <= N <= 10,000)只奶牛非常興奮，因為這是舞會之夜！她們穿上禮服和新鞋子，別 上鮮花，她們要表演圓舞.

只有奶牛才能表演這種圓舞.圓舞需要一些繩索和一個圓形的水池.奶牛們圍在池邊站好， 順時針順序由1到N編號.每只奶牛都面對水池，這樣她就能看到其他的每一只奶牛.

為了跳這種圓舞，她們找了 M(2

#include<iostream>
#include<cstdio>using namespace std;
const int MAXN = 10005;struct Edge{int nxt,to;
}edge[MAXN*5];int n,m,head[MAXN],low[MAXN],dfn[MAXN];
int cnt,num,ans,top,stack[MAXN];
bool vis[MAXN];inline void add(int bg,int ed){edge[++cnt].to=ed;edge[cnt].nxt=head[bg];head[bg]=cnt;
}inline void tarjan(int u){vis[u]=1;stack[++top]=u;dfn[u]=low[u]=++num;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]); }else if(vis[v])low[u]=min(low[u],dfn[v]); }if(low[u]==dfn[u]){if(stack[top]!=u)ans++;vis[u]=0;while(stack[top]!=u){vis[stack[top]]=0;top--;}top--;}
}int main(){scanf("%d%d",&n,&m);for(register int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}for(register int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);printf("%d",ans);return 0;
}