적색 경보

진급 실험 6 - 3.1 적색 경보 (25 분) 전쟁 에서 각 도시 간 의 연관 성 을 유지 하 는 것 이 중요 하 다.이 문 제 는 한 도 시 를 잃 고 국가 가 연결 되 지 않 는 여러 지역 으로 분 단 될 때 빨간색 경 보 를 보 내 는 경보 프로그램 을 만들어 달라 고 요구 했다.주의: 만약 에 이 나라 가 원래 완전히 연결 되 지 않 고 분 단 된 k 개 지역 이 며 한 도 시 를 잃 고 다른 도시 간 의 연결 성 을 바 꾸 지 않 는 다 면 경 보 를 보 내지 마 세 요.
입력 형식: 첫 번 째 줄 에 입력 하면 두 개의 정수 N (0 < N ≤ 500) 과 M (≤ 5000) 을 주 고 각각 도시 개수 (따라서 기본 도시 가 0 에서 N - 1 번호) 와 두 도 시 를 연결 하 는 통로 개수 입 니 다.그 다음 에 M 줄 은 각 줄 에 하나의 통로 로 연 결 된 두 도시 의 번 호 를 주 고 그 사이 에 하나의 빈 칸 으로 구분 된다.도시 정보 다음 에 점령 당 한 정보, 즉 정정 수 K 와 그 다음 에 점령 당 한 K 개 도시 의 번 호 를 제시한다.
주의: 공격 당 하 는 도시 번 호 를 입력 하 는 것 은 모두 합 법 적 이 고 중복 되 지 않 지만 제 시 된 통로 가 중복 되 지 않 는 다 는 것 을 보장 하지 않 습 니 다.
출력 형식: 모든 점령 된 도시 에 대해 국가 전체의 연결 성 을 바 꿀 수 있다 면 Red Alert: City k is lost!,그 중에서 k 는 이 도시 의 번호 이다.그렇지 않 으 면 City k is lost 만 출력 하면 됩 니 다.만약 그 나라 가 마지막 도 시 를 잃 었 다 면, 한 줄 의 수출 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.

이 문 제 는 바로 연결 분량 에 관 한 문제 로 도시 의 연결 성의 강약 은 연결 분량 의 크기 를 통 해 반영 할 수 있다.(연결 분량 이 클 수록 전체적인 연결 성 은 낮 아진 다) 만약 에 한 도 시 를 잃 으 면 그림 에서 이 도시 와 연 결 된 구간 이 모두 끊 어 진 것 으로 나타난다. 만약 에 이 도 시 를 잃 으 면 연결 분량 이 1 만 증가한다. 즉, 이 도시 자체 에 만 영향 을 주 고 전체적인 연결 성에 영향 을 주지 않 으 면 'City x is lost' 를 수출 한다."이 도 시 를 잃 은 후 연결 분량 이 2 를 넘 으 면 전체적인 연결 성 이 영향 을 받 았 음 을 증명 하고 연결 성 이 떨 어 지면 수출" Red Alert: City x is lost! "

#include
#include
using namespace std;
int N,M;
vector<vector<int>> edges;
void DFS(int v,bool *visited)
{
     
	visited[v]=true;
	for(int j=0;j<N;j++)
	{
     
		if(!visited[j]&&edges[v][j]==1)
		{
     
			DFS(j,visited);
		}
	}
}
int DFSTraverse()
{
     
	int cnt=0;
	bool *visited=new bool[N];
	for(int i=0;i<N;i++)
	{
     
		visited[i]=false;
	}
	for(int i=0;i<N;i++)
	{
     
		if(!visited[i]){
     
			DFS(i,visited);
			cnt++;
		}
	}
	return cnt;
}
int main()
{
     
	cin>>N>>M;
	int cnt1=0,cnt2=0;
	edges.resize(N);
	for(int i=0;i<N;i++)
	{
     
		edges[i].resize(N);
	}
	for(int i=0;i<N;i++)
	{
     
		for(int j=0;j<N;j++)
		{
     
			edges[i][j]=0;
		}
	}
	for(int i=0;i<M;i++)
	{
     
		int va,vb;
		cin>>va>>vb;
		edges[va][vb]=edges[vb][va]=1;
	}
	cnt1=DFSTraverse();
	int K;
	cin>>K; 
	for(int i=0;i<K;i++)
	{
     
		int city;
		cin>>city;
		for(int j=0;j<N;j++)
		{
     
			edges[city][j]=0;
			edges[j][city]=0;
		}
		cnt2=DFSTraverse();
		 
		if(cnt2-1>cnt1) printf("Red Alert: City %d is lost!
",city);
		else printf("City %d is lost.
",city);
		cnt1=cnt2;
		if(i==N-1) break;	
	}
	if(K==N) printf("Game Over.
");
	return 0;
}