Box and Ball
题目描述
We have N boxes, numbered 1 through N. At first, box 1 contains one red ball, and each of the other boxes contains one white ball.
Snuke will perform the following M operations, one by one. In the i-th operation, he randomly picks one ball from box xi, then he puts it into box yi.
Find the number of boxes that may contain the red ball after all operations are performed.
Constraints
2≤N≤10 5
1≤M≤10 5
1≤xi,yi≤N
xi≠yi
Just before the i-th operation is performed, box xi contains at least 1 ball.
Snuke will perform the following M operations, one by one. In the i-th operation, he randomly picks one ball from box xi, then he puts it into box yi.
Find the number of boxes that may contain the red ball after all operations are performed.
Constraints
2≤N≤10 5
1≤M≤10 5
1≤xi,yi≤N
xi≠yi
Just before the i-th operation is performed, box xi contains at least 1 ball.
输入
The input is given from Standard Input in the following format:
N M
x1 y1
:
xM yM
N M
x1 y1
:
xM yM
输出
Print the number of boxes that may contain the red ball after all operations are performed.
样例输入
3 2
1 2
2 3
样例输出
2
提示
Just after the first operation, box 1 is empty, box 2 contains one red ball and one white ball, and box 3 contains one white ball.
Now, consider the second operation. If Snuke picks the red ball from box 2, the red ball will go into box 3. If he picks the white ball instead, the red ball will stay in box 2. Thus, the number of boxes that may contain the red ball after all operations, is 2.
这是我的代码。我的队友刚开始并没有先标记再遍历
#include <bits/stdc++.h> using namespace std; struct data { int sum=0; int red=0; }s[100005]; int main() { ios::sync_with_stdio(false); int n,m,i; cin>>n>>m; s[1].sum=s[1].red=1; for(i=2;i<=n;i++) s[i].sum=1; int x,y,ans=0; while(m--){ cin>>x>>y; if(s[x].red==1&&s[x].sum==1){ s[y].red=1; s[x].sum=s[x].red=0; s[y].sum++; } else if(s[x].red==0&&s[x].sum!=0){ s[y].sum++; s[x].sum--; } else if(s[x].red==1&&s[x].sum>1){ s[x].sum--; s[y].red=1; s[y].sum++; } } for(i=1;i<=n;i++){ if(s[i].red==1) ans++; } cout<<ans<<endl; return 0; }
