F题:https://ac.nowcoder.com/acm/contest/12794/F
题目大意:
该题就是给了n个样例,给出m对的节点连接情况,让你判断有多少个连接集团,以及有多少带环集团。
思路:
这题很显然运用到了并查集,通过并查集寻找集团个数,只需要寻找遍历节点,寻找有多少个父节点就是其本身的点,其次就是并查集找环,可以通过数组记录,在节点合并时进行记录,便可得到存在环的父节点。
解题代码:
#include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <set> #include <vector> using namespace std; const long long N = 1005; const int maxn = 2e5 + 5; const long long INF = 8e18; typedef long long ll; #define for0(i,n) for(int i = 0;i < n;i++) #define for1(i,n) for(int i = 1;i <= n;i++) int fa[N],vis[N],sig[N]; int Find(int x) { if(fa[x] == x) return x; else return fa[x] = Find(fa[x]); } void hebing(int x,int y){ int fx = Find(x); int fy = Find(y); if(fx != fy){ fa[fx] = fy; if(sig[fx]){ sig[fy]=1; } } else{ sig[fx]=1; } } int main() { int n; cin >> n; for(int i=1;i <= n;i++){ int s,c,num = 0; cin >> s >> c; for(int j=0;j <= s;j++){ fa[j]=j; vis[j]=0; sig[j]=0; } int x,y; for(int j=0;j < c;j++){ cin >> x >> y; vis[x]=1; vis[y]=1; hebing(x,y); } int tot=0; for(int j=1;j <= s;j++){ if(j == fa[j] && vis[j]){ tot++; if(sig[j] == 1){ num++; } } } printf("Night sky #%d: %d constellations, of which %d need to be fixed.\n\n",i,tot,num); } return 0; }