PAT 1013

题目 ： Battle Over Cities

分值 ： 25
难度 ： 中等题
思路 ： 每次一个点废弃，然后轮询M条边，看看有几条最小生成树可用边，然后打印N-2-cuont
坑点 ： 边界问题，1001个点，边最多可能就是1001*1001条，因此边数组要开大一点。
评语 ： 对我而言还简单，因为最小生成树比较熟悉，然后就是边数组不够大让我两次才AC，略遗憾

具体代码如下

并叉集 + 最小生成树可用边计数 cnt 应该有 N-2条变 ,所以需要 N-2-cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std ;
typedef struct Edge{
    int c1 ;
    int c2 ;
}Ways ;
Ways data[500001] ;
int source[1001] ;
int find_source(int x)
{
    if( source[x] == 0)
        return x ;
    return source[x] = find_source( source[x] ) ;
}
int main() {
    int N ,M ,K ;
    cin >>N>>M >>K ;
    for(int i = 0 ; i<M ;i++)
    {
        cin >>data[i].c1>> data[i].c2 ;
    }
    for(int i = 0 ; i<K ;i++)
    {
        int temp ;
        cin>> temp ;
        for(int i = 1 ; i<= N ; i++)
            source[i] =0;
        int count = 0 ;
        for(int i = 0 ; i< M; i++)  //遍历 M条边  如果存在temp点 直接跳过
        {
            if(data[i].c1 == temp || data[i].c2 == temp)
                continue;
            int source1 = find_source( data[i].c1 );
            int source2 = find_source( data[i].c2 );
            if(source1 != source2 )
            {
                count ++ ;
                source[source1] = source2 ;
            }
        }
        cout<< N-1-1-count <<endl ;
    }
}

Dfs实现联通集的计数,条数就是联通集个数 n-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<vector>
using namespace std;
vector <vector<int>> Map ;
bool flag[1001] ;
void Dfs(int pos)
{
    flag[pos]=true ;
    for(int i = 0 ; i<Map[pos].size() ;i++)
    {
        int x= Map[pos][i] ;
        if(flag[Map[pos][i]]) continue ;
        Dfs(Map[pos][i]);
    }
    return ;
}
int main()
{
    int N ,M , K,c1,c2,t;
    cin >> N >> M >> K ;
    Map.resize(N+1);
    for(int i = 0 ;i < M ; i++)
    {
        scanf("%d%d",&c1,&c2);
        Map[c1].push_back(c2);
        Map[c2].push_back(c1);
    }
    for(int i = 0; i< K ; i++)
    {
        fill(flag,flag+1001 , false );
        cin>> t;
        int cnt = 0 ;
        flag[t] = true ;
        for(int j=1 ; j<=N ; j++)
        {
            if(flag[j]) continue;
            Dfs(j);
            cnt ++ ;
        }
        printf("%d\n",cnt-1) ;
    }
}