看到这道题，首先想到的就是模拟，用一个图来存所有基地和路的状态。

• 对于撤军操作，一个基地撤军后不一定会使这个基地失守，需要判断是否还有仍有驻军的基地与其相连。

• 对于修路操作，这会增加一条边，注意到这条边连接的一定是两个仍有驻军的基地，因此该操作本身不会对基地是否失守产生影响，但是会影响其他操作是否会让基地失守。

• 对于炸毁道路操作，还是不一定会让基地失守，还是要判断。

这么想实在太麻烦了，不如反着考虑。

先把m个操作模拟一遍，并先不判断基地是否失守，这样我们会得到一个最终的图，以样例为例（下面表红的点表示该基地还有驻军，不标红说明没有驻军了。

如果此时仍旧有一些基地有驻军（比如上面的点1），那么我们就从这些基地，沿着仍然存在的边开始DFS，这样便能找出所有一直未失守的基地。

然后，将m个操作倒着模拟一遍，看看哪一个操作过后这个基地“不再失守”（当然，就像正着模拟的时候一个基地如果失守了就永远失守了一样，如果倒着模拟的时候一个基地“不再失守”，那么它之后也不会失守了）：

• 撤军操作（0号操作）：变为驻军操作，让一个本来没有驻军的基地有驻军，随后如果这个点自这个操作以后“不再失守”，再从这个点进行dfs，更新其他点的状态。

• 修路操作（1号操作）：变为“拆路”操作，不难看出，因为这个操作影响都是两个有驻军的基地之间的路，因此有没有这条路都无所谓了。举个例子方便理解：

• 不难看出，如果去掉绿色的边，对于其他的基地是否“失守”没有任何影响，甚至对于之后的操作也没有什么影响。因为两个已经有驻军的基地本身就已经不可能失守了，它们是否联通意义不大，而与这两个基地相连的基地，也不会因为它们是否联通而影响是否失守的状态。因此，这个操作完全可以忽略掉。

• 炸毁道路（2号操作）：变为修路操作，这样便是添加了一条边，此时我们就需要看看这条边能否让失守的基地不再失守。

• 具体来讲，如果这条边连着两个没失守的基地，那么无需再进行其他操作。

• 如果一个基地连着一个没失守的基地和一个目前处于失守状态的基地，那么那个处于失守状态的基地将“不再失守”，随后再从这个基地进行dfs，更新其他基地的状态。

• 如果一个点连着两个仍处于失守状态的点，那么不进行dfs，但是要把这两个点连上。

下面是c++实现代码：

#include<bits/stdc++.h>
using namespace std;
int o[200009],x[200009],y[200009],rd[200009];
vector<int> a[200009];
int cnt[200009];
bool v[200009],r[200009],vv[200009];
int ans[200009];
void dfs(int l,int num){
	if(vv[l]==1){
		return ;
	}
	vv[l]=1;
	ans[l]=num;
	int len=a[l].size();
	for(int i=0;i<len;i++){
		dfs(a[l][i],num);
	}
}
int main(){
	memset(ans,255,sizeof(ans));
	int n,m;
	scanf("%d%d",&n,&m);
	int nr=0;
	for(int i=1;i<=m;i++){
		scanf("%d",&o[i]);
		if(o[i]==0){
			scanf("%d",&x[i]);
			v[x[i]]=1;
		}
		else if(o[i]==1){
			scanf("%d%d",&x[i],&y[i]);
			nr++;
			rd[nr]=i;
		}
		else{
			scanf("%d",&x[i]);
			r[x[i]]=1;
		}
	}
	for(int i=1;i<=nr;i++){
		if(r[i]==0){
			a[x[rd[i]]].push_back(y[rd[i]]);
			a[y[rd[i]]].push_back(x[rd[i]]);
		}
	}
	for(int i=1;i<=n;i++){
		if(v[i]==0){
			dfs(i,0);
		}
	}
	for(int i=m;i>=1;i--){
		if(o[i]==0){
			if(vv[x[i]]==0){
				dfs(x[i],i);
			}
		}
		else if(o[i]==2){
			a[x[rd[x[i]]]].push_back(y[rd[x[i]]]);
			a[y[rd[x[i]]]].push_back(x[rd[x[i]]]);
			if(vv[x[rd[x[i]]]]==1){
				dfs(y[rd[x[i]]],i);
			}
			else if(vv[y[rd[x[i]]]]==1){
				dfs(x[rd[x[i]]],i);
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
} 

时间复杂度：可以看出，每个点只会被dfs一次，因此dfs的时间复杂度为O(n)。而模拟一遍操作的复杂度为O(m)，因此整体复杂度约为O(n+m)，常数也不大，这样便AC了这道题。