题目链接:http://pat.zju.edu.cn/contests/pat-a-practise/1013
并查集
// 思绪太乱,没有想好就写 // 另外,所用变量名字,大小写都出现,生出不少端倪 // 图的并查集问题有些生疏 // // 本题思路: // 1.去掉被占领城市所有的边,计算合并次数ans, // 则ans-1为结果(去掉连通占领城市的边) // 2.合并时,跳过被占领的城市 #include <stdio.h> #define SIZE 1000+10 #define INF -1 int map[SIZE][SIZE], nmap[SIZE][SIZE]; int n, m, K; int fa[SIZE]; int getfa(int x) { if(x == fa[x]) return x; else fa[x] = getfa(fa[x]); return fa[x]; } void Init() { int i; for(i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i != j) { map[i][j] = INF; } else { map[i][j] = 0; } } } return ; } void Initfa() { int i, j; for(i=1; i<=n; i++) { fa[i] = i; } for(j=1; j<=n; j++) { int k; for(k=j; k<=n; k++) { int a= getfa(j); int b= getfa(k); if(nmap[j][k] == 1) { fa[b] = a; } } }// 连通的节点合并 return ; } void newMap(int city) { int i, j; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(i == city || j == city) { nmap[i][j] = INF; } else { nmap[i][j] = map[i][j]; } } } return ; } void Printmap(int map[SIZE][SIZE]) { int i, j; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { printf("%2d ", map[i][j]); } printf("\n"); } return ; } int main() { #ifdef ONLINE_JUDGE #else freopen("E:\\in.txt", "r", stdin); // freopen("E:\\out.txt", "w", stdout); #endif scanf("%d%d%d", &n, &m, &K); Init(); int i, c1, c2; for(i=0; i<m ; i++) { scanf("%d%d", &c1, &c2); map[c1][c2] = map[c2][c1] = 1; } // Printmap(map); while(K-->0) { if(n <= 2) { printf("0\n"); continue; } int lc;//losted city scanf("%d", &lc); newMap(lc); Initfa(); // printf("\n"); // Printmap(nmap); int ans=0, j; for(j=1; j<=n; j++) { if(j == lc) { continue; } int k; for(k=j; k<=n; k++) { if(k ==lc) { continue; } int a= getfa(j); int b= getfa(k); if(a != b) { ans++; fa[b] = a; } } } printf("%d\n", ans); } return 0; }