[POI2007]BIU-Offices

我的第一份代码是这么写的

邻接矩阵存图，手写栈存点

#include<bits/stdc++.h>
using namespace std;
int n,m;
int to[4000005],ne[4000005],f[4000005],cnt;
inline void link(int x,int y){
	to[++cnt]=y;
	ne[cnt]=f[x];
	f[x]=cnt;
}
int stk[100005],top,stk2[100005],top2;
bool vis[100005],vis1[100005];
int ans[100005],k;
queue<int> q;
inline void bfs(int u){
	q.push(u);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=1;ans[k]++;
		for(int i=f[x];i;i=ne[i])vis1[to[i]]=1;
		for(int i=0;i<top;i++){
			if(stk[i]==u)continue;
			if(vis1[stk[i]])stk2[top2++]=stk[i];
			else q.push(stk[i]);
		}
		for(int i=f[x];i;i=ne[i])vis1[to[i]]=0;
		swap(stk,stk2);
		top=top2;top2=0;
	}k++;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y);link(y,x);
	}
	for(int i=1;i<=n;i++)stk[top++]=i;
	for(int i=1;i<=n;i++)if(!vis[i])bfs(i);
	sort(ans,ans+k);
	printf("%d\n",k);
	for(int i=0;i<k;i++)printf("%d ",ans[i]);
	return 0;
}

T了2个点，改成vector存图还是T两个，但第二个点稍微快了一点

把手写栈改成vector就过了，如果把答案数组换成vector还会更快

难道vector的复制能比手写栈直接换指针快？？？

	swap(stk,stk2);
	top2=top;top=0;

	vector<int>tmp=s;s.clear();

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> g[100005];
vector<int>s;
int stk[100005],top,stk2[100005],top2;
bool vis[100005],vis1[100005];
vector<int> ans;
queue<int> q;
inline int bfs(int u){
	int tot=0;
	q.push(u);vis1[u]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=1;tot++;
		for(int i=0;i<g[x].size();i++)vis1[g[x][i]]=1;
		vector<int>tmp=s;s.clear();
		for(int i=0;i<tmp.size();i++){
			if(vis1[tmp[i]])s.push_back(tmp[i]);
			else q.push(tmp[i]);
		}
		for(int i=0;i<g[x].size();i++)vis1[g[x][i]]=0;
	}k++;
	return tot;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)s.push_back(i);
	for(int i=1;i<=n;i++)if(!vis[i])ans.push_back(bfs(i));
	sort(ans.begin(),ans.end());
	printf("%d\n",k);
	for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);
	return 0;
}