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