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;
}
