Description
约翰的N(2≤N≤10000)只奶牛非常兴奋,因为这是舞会之夜!她们穿上礼服和新鞋子,别上鲜花,她们要表演圆舞.
只有奶牛才能表演这种圆舞.圆舞需要一些绳索和一个圆形的水池.奶牛们围在池边站好,顺时针顺序由1到N编号.每只奶牛都面对水池,这样她就能看到其他的每一只奶牛.为了跳这种圆舞,她们找了M(2≤M≤50000)条绳索.若干只奶牛的蹄上握着绳索的一端,绳索沿顺时针方绕过水池,另一端则捆在另一些奶牛身上.这样,一些奶牛就可以牵引另一些奶牛.有的奶牛可能握有很多绳索,也有的奶牛可能一条绳索都没有握。比如说贝茜,她的圆舞跳得是否成功,可以这样检验:沿着她牵引的绳索,找到她牵引的奶牛,再沿着这只奶牛牵引的绳索,又找到一只被牵引的奶牛,如此下去,若最终能回到原位,则她的圆舞跳得成功,因为这一个环上的奶牛可以逆时针牵引而跳起旋转的圜舞.如果不能回到原位,那她的圆舞是不成功的.
如果两只成功跳圆舞的奶牛有绳索相连,那她们可以同属一个组合.
给出每一条绳索的描述,请找出,成功跳了圆舞的奶牛有多少个组合?
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.
第1行输入N和M,接下来M行每行两个整数A和B,表示A牵引着B.
Output
* Line 1: A single line with a single integer that is the number of groups successfully dancing the Round Dance.
成功跳圆舞的奶牛组合数.
Sample Input
5 4
2 4
3 5
1 2
4 1
2 4
3 5
1 2
4 1
INPUT DETAILS:
ASCII art for Round Dancing is challenging. Nevertheless, here is a
representation of the cows around the stock tank:
_1___
/**** \
5 /****** 2
/ /**TANK**|
\ \********/
\ \******/ 3
\ 4____/ /
\_______/
Sample Output
1
HINT
1,2,4这三只奶牛同属一个成功跳了圆舞的组合.而3,5两只奶牛没有跳成功的圆舞
题解
可能有其他dfs的做法,不过我觉得强连通分量直观可靠,所以就打了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define inf 1<<30 #define ll long long using namespace std; int n,m,zz,head[10002]; struct bian {int to,nx;} e[50002]; int pre[10002],low[10002],scc,ct,sccnum[10002]; int stack[10002],top,have[10002],ans; void insert(int x,int y) {zz++; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;} void init() { scanf("%d%d",&n,&m); int i,x,y; for(i=1;i<=m;i++) {scanf("%d%d",&x,&y); insert(x,y); } } void dfs(int x) { pre[x]=low[x]=++ct; stack[++top]=x; int i,p; for(i=head[x];i;i=e[i].nx) {p=e[i].to; if(!pre[p]) {dfs(p); low[x]=min(low[x],low[p]);} else if(!sccnum[p]) low[x]=min(low[x],pre[p]); } p=-1; if(pre[x]==low[x]) {scc++; while(p!=x) {p=stack[top]; top--; sccnum[p]=scc; have[scc]++; } } } void targan() { int i; for(i=1;i<=n;i++) {if(!pre[i]) dfs(i);} for(i=1;i<=scc;i++) {if(have[i]>1) ans++;} printf("%d\n",ans); } int main() { init(); targan(); return 0; }