每天打卡一小时 第十七天 编译四部曲

第一部曲 自然语言

路线图分块，能走通的节点合并为一块，记块的总数为num1。然后去掉一个节点后，再次分块，记块的总数为num2。如果num2-1（去掉了单独的一个节点）与num1相等或num2（去掉该节点之后，该节点所在的块仍互通）等于num1，则不影响连通性。

第二部曲 流程图

第三部曲 代码

#include<iostream>
using namespace std;

int father[501];
int N,M;
int visit[501]; 

struct data{//记道路
	int x;
	int y;
};

int find(int x){
	while(father[x] != x){
		x = father[x];
	}
	return x;
}

void add(int x,int y){
	int x1 = find(x);
	int y1 = find(y);
	if(x1 != y1){
		father[x1] = y1;
	}
}

int main(){
	cin>>N>>M;
	int a,b;
	struct data node [M];
	for(int i=0;i<N;i++){
		father[i] = i;
	}
	for(int i=0;i<M;i++){
		cin>>a>>b;
		node[i].x = a;
		node[i].y = b;
		add(a,b);//合并节点，将可以连通的节点合并
	}
	int num1 = 0;
	for(int i=0;i<N;i++){
		if(father[i] == i){
			num1++;//统计块的个数
		}
	}
	int K;
	cin>>K;int n;
	for(int j=0;j<K;j++){
		cin>>n;
		//重新计算num
		for(int i=0;i<N;i++){
			father[i] = i;
		}
		visit[n] = 1;//这个数组的作用是，标记删除过的节点
		for(int i=0;i<M;i++){
			if(visit[node[i].x] == 1 || visit[node[i].y] == 1){
				continue;//结束本次循环，进行下次循环
			}
			add(node[i].x,node[i].y);//合并没有被删除过的节点
		}
		int num2 = 0;
		for(int i=0;i<N;i++){
			if(father[i] == i){
				num2++;
			}
		}
		if(num2-1 == num1 || num2 == num1){
			cout<<"City "<<n<<" is lost."<<endl;
		}else{
			cout<<"Red Alert: City "<<n<<" is lost!"<<endl;
		}
		num1 = num2;
	}
	if(K >= N)cout<<"Game Over."<<endl;
	
	return 0;
}

第四部曲 总结

看着人家的代码写出来的，好难