请人做网站,学做粤菜的网站有哪些,潍坊比较大的网站制作公司,上海网站设计建设公C: City 时间限制: 1 s 内存限制: 128 MB 题目描述 如果城市A和城市B互通#xff0c;城市B和城市C互通#xff0c;那么城市A和城市C也互通#xff0c;A、B、C三个城市算一个聚集点。先已知有n个城市和m条道路#xff0c;想求的是有几个聚集点#xff1f;但小S觉…C: City 时间限制: 1 s 内存限制: 128 MB 题目描述 如果城市A和城市B互通城市B和城市C互通那么城市A和城市C也互通A、B、C三个城市算一个聚集点。先已知有n个城市和m条道路想求的是有几个聚集点但小S觉得太简单了由于战争原因某些城市会被导弹销毁掉与之相应的道路也变得不可用。之前已经被销毁的不会被复原。现给定每次销毁的城市顺序求每次销毁后聚集点有多少个。 输入 第一行输入n 和m表示城市数量和道路数量(1≤n≤1041≤m≤2n) 接下来m 行每行输入两个数ai和bi (1≤ai,bi≤n) 。表示ai和bi直接有道路 第m2 行输入q表示有q个城市会被销毁 (1≤q≤n) 接下来输入q 个数每行输入一个不重复的数表示被销毁的城市 输出 输出一行q个数每i个数表示第i个城市销毁后聚集点的数量 样例输入 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 #includeiostream
#includestring.h
#includemath.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()//初始化集合每个元素的根节点都是自己
{for (int i 1; i n; i){p[i] i;}
}int find(int x)//查找元素x的根节点是谁
{if (x p[x])return x;elsereturn p[x] find(p[x]);
}void join(int x, int y)//合并两个集合
{int xRoot find(x);int yRoot find(y);if (xRoot yRoot) //根节点相同不合并return;if (r[xRoot] r[yRoot]) //r[i]是元素i所在树的高度矮树的根节点认高树的根节点做根节点p[xRoot] yRoot;else if (r[xRoot] r[yRoot])p[yRoot] xRoot;else{p[yRoot] xRoot;//树高相同做根节点的树高度要加一r[xRoot];}
}
void num()//求不同子集个数
{for (int i 1; i n; i)//有多少个p[i]i,就有多少个子集{if (p[i] i vis[i] 0)t;}
}
bool sameRoot(int x, int y)//查询两个元素的老板是否相同
{return find(x) find(y);
}
int main()
{scanf(%d%d, n, m);init();cnt n;//当元素各不相连的时候有n个集合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;//销毁所有c[i]元素之后可以构成几个子集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转载于:https://www.cnblogs.com/-citywall123/p/10729243.html
