题目描述
就是检查变量a赋值给变量b的时候,变量a是不是已经初始化,如果没有a初始化,那么他就没有资格赋值给其他变量。在正常编译的时候也会报错。
样例
blablabla
算法1
(暴力枚举) $O(n)$
我这里用一个布尔数组a[N]储存每一个变量,下标便表示变量编号,因为对于每一个变量来说只有两种状态,要么就是已经初始化true,要么就就是没有false。
思路:X/Y分别表示左值与右值,只需要检查a[Y]是否已经初始化,也就是检查Y是否为true或者是0(0表示常量),用res表示赋值正确的初始化查询数量,如果a[Y]==true则res++。最后答案就是k-res.
这个题目要注意的是,无论Y是否已经初始化,在之后的查询中X都被视为已经被成功初始化了(题目意思),就是说,只要X曾经做过左值,我们就认为X是初始化了的。所以对每一次查询,都有a[X]=true,表示编号为的变量已经被初始化成功。
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
bool a[N];
int main(){
int n,k;
cin>>n>>k;
int res=0;
for(int i=0;i<k;i++){
int x,y;
cin>>x>>y;
if(a[y]||y==0){
res++;
}
a[x]=true;
}
cout<<k-res;
return 0;
}
``````
#### 参考文献
#### C++ 代码
blablabla
```