Solving graph problems with union search set

6-2-3 Depth-first search Red Alert (25 branch )

It's very important to maintain connectivity between cities in the war . This question asks you to write an alarm program , When the loss of a city causes the country to be divided into multiple disconnected areas , Just a red alert . Be careful ： If the country is not fully connected , It's divided k Regions , The loss of one city does not change the connectivity between other cities , Then don't alarm .

Input format ：

Enter two integers in the first line N（0 < N ≤ 500） and M（≤ 5000）, They are the number of cities （ So the default city is from 0 To N-1 Number ） And the number of roads connecting the two cities . And then M That's ok , Each line gives the number of the two cities connected by a road , In the meantime 1 Space separation . Give the captured information after the city information , It's a positive integer K And then K The number of the captured cities .

Be careful ： Input the number of the occupied city to ensure that it is legal and no repetition , But there is no guarantee that the given path is not repeated .

Output format ：

For every captured city , If it changes the connectivity of the whole country , The output Red Alert: City k is lost!, among k It's the number of the city ; Otherwise, only output City k is lost. that will do . If the country loses its last city , Then add a line of output Game Over..

sample input ：

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

sample output ：

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

#include<iostream>
using namespace std;
int map[520][520];// Build a diagram //
int pre[520];// Previous node of this node 
int n, m;// Number of cities and number of roads 
void inis(int n);// Initialize the join lookup set 
void join(int x, int y);// Building relationships 
int find(int x);// Find the home of the node 
int main()
{
    
    cin >> n>>m;
    int i = 0;
    int a1, a2;// Two cities 
    inis(n);// Initialize and query set 
    for (i = 0; i < m; i++) {
    
        cin >> a1 >> a2;
        map[a1][a2] = map[a2][a1] = 1;// Construct a phase free diagram 
        join(a1, a2);// Build the relationship between the two cities 
    }
    int cout1 = 0, cout2 = 0;//cout1 Record the number of city groups last time ,cout2 Record the number of current city groups 
    for (i = 0; i < m; i++) {
    
        if (pre[i] == i) cout1++;// If this condition is met, it is a city group 
    }
    int del;// Delete the number of cities 
    cin >> del;
    int data;// Deleted city 
    for (int j = 0; j < del; j++) {
    
        cin >> data;
        cout2 = 0;
        inis(n);// And search set initialization 
        for (i = 0; i < n; i++) {
    
            map[data][i] = map[i][data] = 0;// The relationship between the city to be deleted and other cities shall be abolished 
        }
        for (i = 0; i < n; i++) {
    
            for (int k=0; k < n; k++) {
    
                if (map[i][k]) join(i, k);// Rebuild the associated union lookup set 
            }
        }
        for (i = 0; i < n; i++) {
    
            if (pre[i] == i) cout2++;// Find out the number of new city groups 
        }
        if (cout2 <= cout1 + 1) printf("City %d is lost.\n", data);
        else printf("Red Alert: City %d is lost!\n", data);
        cout1 = cout2;
    }
    if (del == n) cout << "Game Over.";// If the number of deleted is the same as the number of cities , The game is over 
}
void inis(int n)
{
    
    int i = 0;
    for (i = 0; i < n; i++) {
    
        pre[i] = i;
    }
}
void join(int x, int y)
{
    
    int fx = find(x);
    int fy = find(y);
    if (fy != fx) {
    
        pre[fx] = fy;
    }
}
int find(int x)
{
    
    if (pre[x] == x) return x;
    else return pre[x] = find(pre[x]);// Path compression 
}