【16届蓝桥杯寒假刷题营】第1期DAY4
4.可达岛屿的个数 - 蓝桥云课
题目背景
在一个神奇的魔法世界中，有一座古老的迷幻之城。迷幻之城被分成 n 个鸟屿，编号从 1 到 n，共有 m 座桥。迷幻之城的居民们希望能够建立起紧密的联系，每个岛屿上的居民都想知道自己最多能到达多少个岛屿。
请你编写程序解决这个问题。
输入格式
第一行包含两个整数 n 和 m (1≤n≤105,0≤m≤min105,2n(n−1))，表示鸟屿的数量和桥的数量。接下来 m 行，每行包含两个整数 ui,vi (1≤ui,vi≤n)，表示编号为 ui 和 vi 的岛屿之间有一座桥。
输出格式
输出一行包含 n 个以空格分隔的整数，第 i 个整数表示编号为 i 的鸟屿上的居民最多能到达的鸟屿个数。
样例输入
6 3
1 2
4 5
2 6样例输出
3 3 1 2 2 3思路：
暴力，每一个点开始搜索，然后记录经过多少个点。
代码如下：
#include <iostream>
#include <vector>
#include<queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n,m,tot,sum;
ll head[N];
bool vis[N];
ll distant[N];
struct Edge{ll next;ll to;
}e[2*N];
void add(ll u,ll v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(ll cur)
{if(vis[cur])return;vis[cur] = true;sum++;ll u = head[cur];while(u != -1){ll to = e[u].to;dfs(to);u = e[u].next;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m;memset(head,-1,sizeof(head));for(ll i = 1 ; i <= m ; i++){ll u,v;cin >> u >> v;add(u,v);add(v,u);}for(ll i = 1 ; i <= n ; i++){sum = 0;memset(vis,false,sizeof(vis));dfs(i);distant[i] = sum;}for(ll i = 1 ; i <= n ; i++)cout << distant[i] << " ";return 0;
}
思路：
每一次搜过的点，这些点的能到达的岛都是一样的。其他一样。但是还是超时
代码如下：
#include <iostream>
#include <vector>
#include<queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n,m,tot,sum;
ll head[N];
bool vis[N];
ll distant[N];
struct Edge{ll next;ll to;
}e[2*N];
void add(ll u,ll v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(ll cur)
{if(vis[cur])return;vis[cur] = true;sum++;ll u = head[cur];while(u != -1){ll to = e[u].to;dfs(to);u = e[u].next;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m;memset(head,-1,sizeof(head));for(ll i = 1 ; i <= m ; i++){ll u,v;cin >> u >> v;add(u,v);add(v,u);}for(ll i = 1 ; i <= n ; i++){sum = 0;memset(vis,false,sizeof(vis));if(vis[i])continue;dfs(i);for(ll j = 1 ; j <= n ; j++){if(vis[j])distant[j] = sum;}}for(ll i = 1 ; i <= n ; i++)cout << distant[i] << " ";return 0;
}
思路3：
因为遍历vis数组会变成O(N*N)，所以肯定会超时，所以我是用vector，将联通的岛（点）存进去，最后遍历复制，简短时间。过了。
#include <iostream>
#include <vector>
#include<queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
vector <ll> arr;
const ll N = 1e5+10;
ll n,m,tot,sum;
ll head[N];
bool vis[N];
ll distant[N];
struct Edge{ll next;ll to;
}e[2*N];
void add(ll u,ll v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(ll cur)
{if(vis[cur])return;vis[cur] = true;arr.push_back(cur);sum++;ll u = head[cur];while(u != -1){ll to = e[u].to;dfs(to);u = e[u].next;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m;memset(head,-1,sizeof(head));for(ll i = 1 ; i <= m ; i++){ll u,v;cin >> u >> v;add(u,v);add(v,u);}for(ll i = 1 ; i <= n ; i++){sum = 0;memset(vis,false,sizeof(vis));arr.clear();if(distant[i])continue;dfs(i);for(ll j = 0 ; j < arr.size() ; j++){distant[arr[j]] = sum; }}for(ll i = 1 ; i <= n ; i++)cout << distant[i] << " ";return 0;
}
并查集：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int N = 1e5 + 10;
int fa[N], sz[N];
int n, m;int find(int i)
{if (fa[i] != i) {fa[i] = find(fa[i]); // 递归路径压缩}return fa[i];
}
void set(int u, int v)
{//取出两个节点的根节点 int root_u = find(u);int root_v = find(v);if (root_u != root_v) //如果不在同一个集合 {fa[root_v] = root_u;//将集合root_v接到集合root_u上 sz[root_u] += sz[root_v];//集合root_u的元素数量应加上集合root_v的元素数量 }
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){fa[i] = i;sz[i] = 1;//本身作为一个元素的集合 }for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;set(u, v);}for(int i = 1 ; i <= n ; i++){cout << sz[find(i)] << " ";}return 0;
}
