牛的晚上的集会The

洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom,p2863usaco06jan

ng the other ends of her ropes (if she has any), along with the cows
holding the other ends of any ropes they hold, etc. When Bessie dances
clockwise around the tank, she must instantly pull all the other cows in
her group around clockwise, too. Likewise,

if she dances the other way, she must instantly pull the entire group
counterclockwise (anti-clockwise in British English).

Of course, if the ropes are not properly distributed then a set of cows
might not form a proper dance group and thus can not succeed at the
Round Dance. One way this happens is when only one rope connects two
cows. One cow could pull the other in one direction, but could not pull
the other direction (since pushing ropes is well-known to be fruitless).
Note that the cows must Dance in lock-step: a dangling cow (perhaps with
just one rope) that is eventually pulled along disqualifies a group from
properly performing the Round Dance since she is not immediately pulled
into lockstep with the rest.

Given the ropes and their distribution to cows, how many groups of cows
can properly perform the Round Dance? Note that a set of ropes and cows
might wrap many …

【luogu 2863】[USACO06JAN]牛的晚会The Cow Prom,luoguusaco06jan

The Cow Prom
Description

输入输出格式

输入格式:

牛的晚上的集会The。 

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.

 

输出格式:

 

Line 1: A single line with a single integer that is the number of groups
successfully dancing the Round Dance.

 

难题汇报

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<M<
50000)条绳索.若干只水牛的蹄上握着绳索的单方面,
绳索沿顺时针方绕过水池,另风姿浪漫端则捆在另黄金年代对白牛身上.那样,一些白牛就足以牵引另后生可畏都部队分白牛.有的水牛恐怕持有相当多绳索,也会有的水牛大概一条绳索都没有.

对于壹头白牛,例如说贝茜,她的圆舞跳得是还是不是成功,能够如此查证:沿着她拉住的绳索,
找到她拉住的奶牛,再顺着那只水牛牵引的绳子,又找到贰只被拖曳的水牛,如此下去,若最终能回到贝茜,则她的圆舞跳得成功,因为那叁个环上的白牛能够逆时针牵引而跳起旋转的圆舞.
假使那样的印证不可能完毕,这他的圆舞是不成功的.

比如三只成功跳圆舞的白牛有绳索相连,那她们得以同属二个组合.

交由每一条绳索的描述,请寻觅,成功跳了圆舞的水牛有微微个组成?

For the Round Dance to succeed for any given cow (say, Bessie), the
ropes that she holds must be configured just right. To know if Bessie’s
dance is successful, one must examine the set of cows holding the other
ends of her ropes (if she has any), along with the cows holding the
other ends of any ropes they hold, etc. When Bessie dances clockwise
around the tank, she must instantly pull all the other cows in her group
around clockwise, too. Likewise,

if she dances the other way, she must instantly pull the entire group
counterclockwise (anti-clockwise in British English).

Of course, if the ropes are not properly distributed then a set of cows
might not form a proper dance group and thus can not succeed at the
Round Dance. One way this happens is when only one rope connects two
cows. One cow could pull the other in one direction, but could not pull
the other direction (since pushing ropes is well-known to be fruitless).
Note that the cows must Dance in lock-step: a dangling cow (perhaps with
just one rope) that is eventually pulled along disqualifies a group from
properly performing the Round Dance since she is not immediately pulled
into lockstep with the rest.

Given the ropes and their distribution to cows, how many groups of cows
can properly perform the Round Dance? Note that a set of ropes and cows
might wrap many …

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.

输入输出样例

输入样例#1: 复制

5 4
2 4
3 5
1 2
4 1

输出样例#1: 复制

1

输入输出格式

输入格式:

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.

输出格式:

Line 1: A single line with a single integer that is the number of groups
successfully dancing 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.

说明

Explanation of the sample:

美高梅开户网址,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____/  /
     \_______/

Cows 1, 2, and 4 are properly connected and form a complete Round Dance
group. Cows 3 and 5 don’t have the second rope they’d need to be able to
pull both ways, thus they can not properly perform the Round Dance.

 

强联通分量的裸题

直接出口强联通分量的个数就好

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<stack>
 4 #include<queue>
 5 #include<map>
 6 #include<stack>
 7 #define ls k<<1
 8 #define rs k<<1|1
 9 #define LL long long 
10 using namespace std;
11 const int MAXN=100002;
12 inline int read()
13 {
14     char c=getchar();int x=0,flag=1;
15     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*flag;
17 }
18 struct node
19 {
20     int u,v,nxt;
21 }edge[MAXN];
22 int head[MAXN];
23 int num=1;
24 inline void add_edge(int x,int y)
25 {
26     edge[num].u=x;
27     edge[num].v=y;
28     edge[num].nxt=head[x];
29     head[x]=num++;
30 }
31 int low[MAXN];
32 int dfn[MAXN];//时间戳 
33 int tot=0;
34 stack<int>s;
35 int ans=0;
36 int vis[MAXN];
37 int color[MAXN],colornum=0;
38 int happen[MAXN];
39 inline void Tarjan(int node)
40 {
41     low[node]=dfn[node]=++tot;
42     vis[node]=1;
43     s.push(node);
44     for(int i=head[node];i!=-1;i=edge[i].nxt)
45     {
46         if(!dfn[edge[i].v])
47             Tarjan(edge[i].v),low[node]=min(low[node],low[edge[i].v]);
48         else if(vis[edge[i].v])
49             low[node]=min(low[node],dfn[edge[i].v]);
50     }
51     if(dfn[node]==low[node])
52     {
53         colornum++;
54         int h;
55         do
56         {    
57             h=s.top();
58             if(color[s.top()]==0)    color[s.top()]=colornum;
59             vis[s.top()]=0;
60             s.pop();
61         }while(node!=h);
62     }
63 }
64 int main()
65 {
66     memset(head,-1,sizeof(head));
67     int n=read(),m=read();
68     for(int i=1;i<=m;i++)
69     {
70         int x=read(),y=read();
71         add_edge(x,y);
72     }
73     for(int i=1;i<=n;i++)    
74         if(color[i]==0)
75             Tarjan(i);
76     for(int i=1;i<=n;i++)
77         happen[color[i]]++;
78     int ans=0;
79     for(int i=1;i<=colornum;i++)
80         if(happen[i]>1)
81             ans++;
82     printf("%d",ans);
83     return 0;
84 }

 

[USACO06JAN]牛的晚会The Cow
Prom,p2863usaco06jan ng the other ends of her ropes (if she has any),
along with the cows holding the other ends of any ropes they
hol…

输入输出样例

输入样例#1:

5 4
2 4
3 5
1 2
4 1

输出样例#1:

1

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.

说明

Explanation of the sample:

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____/  /
     \_______/

Cows 1, 2, and 4 are properly connected and form a complete Round Dance
group. Cows 3 and 5 don’t have the second rope they’d need to be able to
pull both ways, thus they can not properly perform the Round Dance.

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stack>
 6 #define maxn 10005
 7 #define maxm 50005
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 struct node{int to,next;}e[maxm];
16 int n,m,cnt,last[maxn],dfn[maxn],low[maxn],idex=0,Bcnt=0,instack[maxn],vis[maxn],ans=0;
17 stack<int> stap;
18 void add(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;}
19 void tarjan(int s){
20     int t;
21     dfn[s]=low[s]=++idex;
22     stap.push(s);
23     instack[s]=1;
24     for(int i=last[s];i;i=e[i].next){
25         t=e[i].to;
26         if(!dfn[t]){
27             tarjan(t);
28             low[s]=min(low[s],low[t]);
29         }
30         else if(instack[t]) low[s]=min(low[s],low[t]);
31     }
32     if(dfn[s]==low[s]){
33         Bcnt++;
34         do{
35             t=stap.top();
36             stap.pop();
37             instack[t]=false;
38             vis[Bcnt]++;
39         }while(s!=t);
40     }
41 }
42 int main(){
43     n=read(),m=read();
44     for(int i=1;i<=m;i++){
45         int u=read(),v=read();
46         add(u,v);
47     }
48     for(int i=1;i<=n;i++)
49         if(!dfn[i])
50             tarjan(i);
51     for(int i=1;i<=Bcnt;i++)
52         if(vis[i]!=1)
53             ans++;
54     printf("%d",ans);
55     return 0;
56 }

2863】[USACO06JAN]牛的晚上的集会The Cow
Prom,luoguusaco06jan 题目陈诉 The N (2 = N = 10,000) cows are so
excited: it’s prom night! They are dressed in their finest go…

For the Round Dance to succeed for any given cow (say, Bessie), the
ropes that she holds must be configured just right. To know if Bessie‘s
dance is successful, one must examine the set of cows holding the other
ends of her ropes (if she has any), along with the cows holding the
other ends of any ropes they hold, etc. When Bessie dances clockwise
around the tank, she must instantly pull all the other cows in her group
around clockwise, too. Likewise,
if she dances the other way, she must instantly pull the entire group
counterclockwise (anti-clockwise in British English).

Of course, if the ropes are not properly distributed then a set of cows
might not form a proper dance group and thus can not succeed at the
Round Dance. One way this happens is when only one rope connects two
cows. One cow could pull the other in one direction, but could not pull
the other direction (since pushing ropes is well-known to be fruitless).
Note that the cows must Dance in lock-step: a dangling cow (perhaps with
just one rope) that is eventually pulled along disqualifies a group from
properly performing the Round Dance since she is not immediately pulled
into lockstep with the rest.

Given the ropes and their distribution to cows, how many groups of cows
can properly perform the Round Dance? Note that a set of ropes and cows
might wrap many times around the stock tank.
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.
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
Sample Output

1

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图