图（graph.cpp）（回归）
目录
（考完CCF回归！）
图（graph.cpp）
【题目描述】
【数据限制及注意点】
【输入格式】
【输出格式】
【样例输入输出】
【样例解释】
代码
（考完CCF回归！）
图（graph.cpp）
【题目描述】
现在有一张N个点的无向图，每个点编号为1~N，在初始条件下没有边。
给出Q个操作并依次执行，每个操作结束后，输出没有和其他任何点相连的点的个数（也即度为0的点的个数）。
操作Queryi只会有以下两种格式：
·1 u v：在点u和点v间连接一条无向边，数据保证在添加此边前，点u和点v没有连边。
·2 v：移除所有与点v相连的边，点v本身不被移除。
【数据限制及注意点】
·2≤N≤3x105；
·1≤Q≤3x105；
·对于第一种操作，保证1≤u,v≤N，且u≠v；
·对于第二种操作保证1≤v≤N；
·在第一种操作第一次出现前，整张图没有任何边存在；
·所有输入都是整数。
【输入格式】
第一行两个正整数N，Q。
接下来N行，每行一个操作Queryi。
【输出格式】
输出Q行，每行一个整数。
【样例输入输出】
| Input | Output | |
| Sample 1 | 3 7 1 1 2 1 1 3 1 2 3 2 1 1 1 2 2 2 1 1 2 | 1 0 0 1 0 3 1 |
| Sample 2 | 2 1 2 1 | 2 |
【样例解释】
| Description | |
| Sample 1 | 操作1过后，点1与点2相连，点3不与任何点相连，所以结果为1。 在前3次操作过后，三个点之间两两相连。 第4次操作过后，点1的所有边被删除，所以点1不与任何点相连，但点2点3仍然存在一条边相连，所以第四次操作的答案是1。 |
| Sample 2 | 略 |
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,fl,x,y,cnt;
set <int> a[300010];
set <int>::iterator it;
main(){
cin>>n>>m;cnt=n;
for(i=1;i<=m;i++){
cin>>fl;
if(fl==1){
cin>>x>>y;
if(a[x].empty()) cnt--;
if(a[y].empty()) cnt--;
a[x].insert(y);a[y].insert(x);
}
else{
cin>>x;
if(!a[x].empty()) cnt++;
for(it=a[x].begin();it!=a[x].end();it++){
a[*it].erase(x);
if(a[*it].empty()) cnt++;
}
a[x].clear();
}
cout<<cnt<<"\n";
}
}
#include <bits/stdc++.h>#define ll long longusing namespace std;ll n,m,i,fl,x,y,cnt;set <int> a[300010];set <int>::iterator it;main(){cin>>n>>m;cnt=n;for(i=1;i<=m;i++){cin>>fl;if(fl==1){cin>>x>>y;if(a[x].empty()) cnt--;if(a[y].empty()) cnt--;a[x].insert(y);a[y].insert(x);}else{cin>>x;if(!a[x].empty()) cnt++;for(it=a[x].begin();it!=a[x].end();it++){a[*it].erase(x);if(a[*it].empty()) cnt++;}a[x].clear();}cout<<cnt<<"\n";}}