L2-013 紅色警報(bào)

分?jǐn)?shù) 25

戰(zhàn)爭(zhēng)中保持各個(gè)城市間的連通性非常重要。本題要求你編寫一個(gè)報(bào)警程序，當(dāng)失去一個(gè)城市導(dǎo)致國(guó)家被分裂為多個(gè)無(wú)法連通的區(qū)域時(shí)，就發(fā)出紅色警報(bào)。注意：若該國(guó)本來(lái)就不完全連通，是分裂的k個(gè)區(qū)域，而失去一個(gè)城市并不改變其他城市之間的連通性，則不要發(fā)出警報(bào)。

輸入格式：

輸入在第一行給出兩個(gè)整數(shù)N（0?<?N?≤?500）和M（≤?5000），分別為城市個(gè)數(shù)（于是默認(rèn)城市從0到N-1編號(hào)）和連接兩城市的通路條數(shù)。隨后M行，每行給出一條通路所連接的兩個(gè)城市的編號(hào)，其間以1個(gè)空格分隔。在城市信息之后給出被攻占的信息，即一個(gè)正整數(shù)K和隨后的K個(gè)被攻占的城市的編號(hào)。

注意：輸入保證給出的被攻占的城市編號(hào)都是合法的且無(wú)重復(fù)，但并不保證給出的通路沒(méi)有重復(fù)。

輸出格式：

對(duì)每個(gè)被攻占的城市，如果它會(huì)改變整個(gè)國(guó)家的連通性，則輸出Red Alert: City k is lost!，其中k是該城市的編號(hào)；否則只輸出City k is lost.即可。如果該國(guó)失去了最后一個(gè)城市，則增加一行輸出Game Over.。

輸入樣例：

5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3

輸出樣例：

City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.

題解?

初始建圖用雙向建邊，然后算一個(gè)初始的連通分量，每次刪城市的時(shí)候重新計(jì)算連通分量，看刪完后的連通分量是否大于原本的+1，因?yàn)槿绻桓淖冞B通性，刪完一個(gè)城市之后，這個(gè)城市單獨(dú)出來(lái)，連通分量+1，其余不變。所以若大于now+1，就說(shuō)明改變了。每次都更新連通分量。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-839092.html

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int n,m;
int g[505][505];
int v[5005];

void dfs(int x)
{
	v[x]=1;
	for(int i=0;i<n;i++)
	{
		if(!v[i] && g[x][i]==1)//這個(gè)點(diǎn)沒(méi)走過(guò)且能走
		{
			dfs(i);
		}
	}
}
//計(jì)算連通分量
int ltfl()
{
	int cnt=0;
	memset(v,0,sizeof(v));
	for(int i=0;i<n;i++)
	{
		if(v[i]==0)
		{
			dfs(i);
			cnt++;
		}
	}
	return cnt;
 } 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a][b]=1;
		g[b][a]=1;
	}
	int k;
	cin>>k;
	int now=ltfl();
    
	int sum=n;
	while(k--)
	{
		int x;
		cin>>x;
		
		for(int i=0;i<n;i++)
		{
			if(g[x][i]==1 || g[i][x]==1)
			{
				g[x][i]=0;
				g[i][x]=0;
			}
			
		}
		int temp=ltfl();
			if(temp>now+1)
			{
				
				cout<<"Red Alert: City "<<x<<" is lost!"<<endl;
			}
			else
			{
				cout<<"City "<<x<<" is lost."<<endl;
			}
        now=temp;
			sum--;
	}
	if(sum==0)
	{
		cout<<"Game Over."<<endl;
	}
	return 0;
}

到了這里，關(guān)于團(tuán)體程序設(shè)計(jì)天梯賽 L2-013 紅色警報(bào)（連通分量）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！