C: City

時(shí)間限制: 1 s ???? 內(nèi)存限制: 128 MB ????

題目描述

? ? ? ?如果城市A和城市B互通，城市B和城市C互通，那么城市A和城市C也互通，A、B、C三個(gè)城市算一個(gè)聚集點(diǎn)。先已知有n個(gè)城市和m條道路，想求的是有幾個(gè)聚集點(diǎn)？但小S覺(jué)得太簡(jiǎn)單了，由于戰(zhàn)爭(zhēng)原因，某些城市會(huì)被導(dǎo)彈銷(xiāo)毀掉，與之相應(yīng)的道路也變得不可用。之前已經(jīng)被銷(xiāo)毀的不會(huì)被復(fù)原。現(xiàn)給定每次銷(xiāo)毀的城市順序，求每次銷(xiāo)毀后聚集點(diǎn)有多少個(gè)。

輸入

第一行輸入n

和m，表示城市數(shù)量和道路數(shù)量(1≤n≤104，1≤m≤2n)

接下來(lái)m

行，每行輸入兩個(gè)數(shù)ai和bi (1≤ai,bi≤n)

。表示ai和bi直接有道路

第m+2

行輸入q，表示有q個(gè)城市會(huì)被銷(xiāo)毀 (1≤q≤n)

接下來(lái)輸入q

個(gè)數(shù)，每行輸入一個(gè)不重復(fù)的數(shù)，表示被銷(xiāo)毀的城市

輸出

輸出一行q個(gè)數(shù)，每i個(gè)數(shù)表示第i個(gè)城市銷(xiāo)毀后聚集點(diǎn)的數(shù)量

樣例輸入

8 9 1 2 1 3 1 6 2 4 3 6 4 5 4 7 5 7 5 8 4 3 2 5 4

樣例輸出

1 2 3 3 ? #include<iostream> #include<string.h> #include<math.h> #define ll long long using namespace std; int a[100005], b[100005], c[100005], p[100005], ans[100005], vis[100005], r[100005]; int n, m, t = 0, cnt; void init()//初始化集合，每個(gè)元素的根節(jié)點(diǎn)都是自己 {for (int i = 1; i <= n; i++){p[i] = i;} }int find(int x)//查找元素x的根節(jié)點(diǎn)是誰(shuí) {if (x == p[x])return x;elsereturn p[x] = find(p[x]); }void join(int x, int y)//合并兩個(gè)集合 {int xRoot = find(x);int yRoot = find(y);if (xRoot == yRoot) //根節(jié)點(diǎn)相同，不合并return;if (r[xRoot] < r[yRoot]) //r[i]是元素i所在樹(shù)的高度，矮樹(shù)的根節(jié)點(diǎn)認(rèn)高樹(shù)的根節(jié)點(diǎn)做根節(jié)點(diǎn)p[xRoot] = yRoot;else if (r[xRoot] > r[yRoot])p[yRoot] = xRoot;else{p[yRoot] = xRoot;//樹(shù)高相同，做根節(jié)點(diǎn)的樹(shù)高度要加一r[xRoot]++;} } void num()//求不同子集個(gè)數(shù) {for (int i = 1; i <= n; i++)//有多少個(gè)p[i]==i,就有多少個(gè)子集 {if (p[i] == i && vis[i] == 0)t++;} } bool sameRoot(int x, int y)//查詢兩個(gè)元素的老板是否相同 {return find(x) == find(y); } int main() {scanf("%d%d", &n, &m);init();cnt = n;//當(dāng)元素各不相連的時(shí)候，有n個(gè)集合for (int i = 1; i <= m; i++){scanf("%d%d", &a[i], &b[i]);}int k;scanf("%d", &k);for (int i = 1; i <= k; i++){scanf("%d", &c[i]);vis[c[i]] = 1;}for (int i = 1; i <= m; i++){if (vis[a[i]] == 0 && vis[b[i]] == 0)join(a[i], b[i]);}num();int base = t;//銷(xiāo)毀所有c[i]元素之后可以構(gòu)成幾個(gè)子集cnt = base;ans[k + 1] = base;for (int i = k; i >= 1; i--){vis[c[i]] = 0;cnt = cnt + 1;ans[i] = cnt;for (int j = 1; j <= m; j++){if (a[j] == c[i] && vis[b[j]] == 0){if (sameRoot(a[j], b[j]))ans[i] = cnt;else{join(a[j], b[j]);{cnt = cnt - 1;ans[i] = cnt;}}}if (b[j] == c[i] && vis[a[j]] == 0){if (sameRoot(a[j], b[j]))ans[i] = cnt;else{join(a[j], b[j]);{cnt = cnt - 1;ans[i] = cnt;}}}}}for (int i = 2; i <= k + 1; i++){printf("%d", ans[i]);if (i != k + 1)printf(" ");}printf("\n");//system("pause");return 0; }

?

相似題目：https://www.cnblogs.com/-citywall123/p/10719924.html

轉(zhuǎn)載于:https://www.cnblogs.com/-citywall123/p/10729243.html

總結(jié)

以上是生活随笔為你收集整理的C: City----逆向并查集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。