7-41 red alert (25 points) (calculate graph connectivity ->dfs)
Published: 2019-04-13

7-41 Red Alert (25 points)

It is very important to maintain connectivity between cities in the war.This topic requires you to write an alarm program that will give a red alarm when the loss of a city causes the country to be divided into several disconnected areas.Note: If the country is not completely connected and is divided into K regions, and the loss of one city does not change the connectivity between other cities, do not issue an alarm.

input format:

input gives two integers n (0 < n ≤ 500) and m (≤ 5000) in the first row, which are respectively the number of cities (hence the default number of cities from 0 to N-1) and the number of passages connecting the two cities.The following m lines, each line gives the number of the two cities connected by a passage, separated by a space.The captured information is given after the city information, i.e. a positive integer k and the number of the following k captured cities.

Note: The input guarantees that the captured city numbers given are legal and not duplicated, but does not guarantee that the given routes are not duplicated.

output format:

for each captured city, if it will change the connectivity of the whole country, output redalert: citykislose!Where k is the number of the city;Otherwise, only citykislose.If the country loses its last city, add a line to export to Game Over.

input sample:

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

Output Sample:

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

Solution: Calculate the city of connected set before the war, and then calculate the current number of connected set cities for each city in Occupation and compare them.If r>count+1, it means that the connectivity of the country has been destroyed. at this time, a red alarm should be issued.At the end of each cycle, count is equal to r (updated to the current city connected set number).If the number of cities in Occupation is equal to the total number of cities in the country, then the game is over and Game Over needs to be exported.

code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int v,e;
int g[505][505];
int vis[505];
int k;
void dfs(int i)
{
	vis[i]=1;
	for(int j=0;j<v;j++)
	  if(g[i][j]==1&&vis[j]==0)
	     dfs(j);
}
//计算连通量 
int unicom()
{
	int sum=0;
	for(int i=0;i<v;i++)
	{
		if(vis[i]==0)
		{
			dfs(i);
			sum++;
		}
	}
	return sum;
}
int main()
{
	cin>>v>>e;
	int t=v; 
	int a,b;
	for(int i=0;i<e;i++)
	{
		scanf("%d%d",&a,&b);
		g[a][b]=g[b][a]=1;
	} 
	int k;
	cin>>k;
	int s=k; 
	int count=unicom();//记录下一开始城市的连通量 
	int num; 
	while(k--)
	{
	    //当城市都被占领完了一切over
		t--;
		if(t<0) break; 
		cin>>num;
		//城市被占领后就变得孤独 
		for(int i=0;i<v;i++)
		{
			g[num][i]=g[i][num]=0;
		}
		memset(vis,0,sizeof(vis));
		int r=unicom();
		if(r>count+1) 
		    printf("Red Alert: City %d is lost!\n",num);
		else 
		    printf("City %d is lost.\n",num);
		count=r;//记得更新当前的连通量 
	}
	if(s>=v) 
	    printf("Game Over.\n");
	return 0;
}