题目分析与思路提示

1. 数据结构：图的存储

由于 $N$ 达到 $10^5$，我们不能使用邻接矩阵（二维数组），会导致空间爆炸 ($10^{10}$)。 必须使用邻接表。在 C++ 中，最常用的方式是 vector<int> adj[N]。

• adj[u] 里面存着所有和 $u$ 结盟的城池编号。

2. 核心算法：BFS 或 DFS

我们的目标是遍历图中的每一个点，并找出它属于哪个圈子。

算法流程：

1. 准备一个 visited 数组，记录每个城池是否被访问过。初始化为 false。
2. 准备两个变量：component_count (集团数) 和 max_size (最大规模)。
3. 遍历所有城池 $i$ 从 1 到 $N$：
   • 如果 visited[i] 为 true：说明这个城池已经被之前的遍历访问过了，属于某个已知的集团，跳过。
   • 如果 visited[i] 为 false：说明发现了一个新的、未探索的同盟集团！
     • component_count 加 1。
     • 启动 BFS/DFS：从 $i$ 开始，顺着边把这个集团里所有人找出来，并标记为 visited。
     • 在搜索过程中统计这个集团的人数 current_size。
     • 更新最大值：max_size = max(max_size, current_size)。

3. 复杂度分析

• 时间复杂度：每个点只会被访问一次，每条边也只会被遍历两次（双向）。总复杂度 $O(N + M)$。对于 $10^5$ 的数据，完全可以秒杀。
• 空间复杂度：邻接表存储 $O(N + M)$。

参考代码 (C++14)

这里提供 BFS (广度优先搜索) 的写法，因为 BFS 使用队列（堆内存），相比递归 DFS（栈内存）更不容易爆栈，适合处理大规模数据。

/**
 * 题目：合纵连横 (Alliance Strategy)
 * 难度：GESP 6级
 * 算法：图的遍历 (BFS), 连通块统计
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 邻接表存储图
vector<int> adj[MAXN];
// 访问标记数组
bool visited[MAXN];

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 1. 读入边，建图
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        // 无向图，双向添加
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int component_count = 0; // 连通块数量
    int max_size = 0;        // 最大连通块的大小

    // 2. 遍历所有节点
    for (int i = 1; i <= N; ++i) {
        // 如果该节点未被访问，说明发现了一个新的连通块
        if (!visited[i]) {
            component_count++;
            
            // --- 开始 BFS ---
            int current_size = 0;
            queue<int> q;
            
            q.push(i);
            visited[i] = true;
            current_size++;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                // 遍历 u 的所有邻居
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true; // 标记访问
                        current_size++;    // 统计大小
                        q.push(v);         // 入队
                    }
                }
            }
            // --- BFS 结束 ---

            // 更新最大规模
            if (current_size > max_size) {
                max_size = current_size;
            }
        }
    }

    cout << component_count << " " << max_size << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。覆盖了稀疏图、稠密图、全连通、全孤立等情况。

/**
 * GESP 6级 [合纵连横] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
const int MAXN_SOLVE = 100005;
vector<int> g_adj[MAXN_SOLVE];
bool g_vis[MAXN_SOLVE];

void solve(int N, const vector<pair<int, int>>& edges, ofstream& fout) {
    // 初始化
    for(int i=1; i<=N; i++) {
        g_adj[i].clear();
        g_vis[i] = false;
    }
    
    for(const auto& e : edges) {
        g_adj[e.first].push_back(e.second);
        g_adj[e.second].push_back(e.first);
    }

    int count = 0;
    int max_sz = 0;

    for(int i=1; i<=N; i++) {
        if(!g_vis[i]) {
            count++;
            int sz = 0;
            queue<int> q;
            q.push(i);
            g_vis[i] = true;
            sz++;
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(int v : g_adj[u]) {
                    if(!g_vis[v]) {
                        g_vis[v] = true;
                        sz++;
                        q.push(v);
                    }
                }
            }
            if(sz > max_sz) max_sz = sz;
        }
    }
    fout << count << " " << max_sz << "\n";
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<pair<int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 6; M = 4;
            edges = {{1,2}, {2,3}, {4,5}, {5,6}};
        }
        else if (i == 2) {
            // 样例2 (包含孤立点)
            N = 5; M = 3;
            edges = {{1,2}, {2,3}, {1,3}};
        }
        else if (i == 3) {
            // 全孤立 (M=0)
            N = 100; M = 0;
        }
        else if (i == 4) {
            // 全连通 (链状)
            N = 1000; M = N-1;
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
        }
        else if (i == 5) {
            // 菊花图 (1连所有)
            N = 1000; M = N-1;
            for(int k=2; k<=N; k++) edges.push_back({1, k});
        }
        else if (i == 6) {
            // 两个大团
            N = 2000; M = 2000;
            // 1~1000 连通
            for(int k=1; k<1000; k++) edges.push_back({k, k+1});
            // 1001~2000 连通
            for(int k=1001; k<2000; k++) edges.push_back({k, k+1});
        }
        else {
            // 大规模随机 (N, M = 10^5)
            N = 100000; 
            if(i == 7) M = 1000; // 稀疏
            else if(i == 8) M = N; // 中等
            else M = 200000; // 稠密

            for(int k=0; k<M; k++) {
                int u = randRange(1, N);
                int v = randRange(1, N);
                if(u != v) edges.push_back({u, v});
            }
        }

        // 写入输入 (使用 \n 优化)
        fin << N << " " << edges.size() << "\n";
        for (const auto& e : edges) {
            fin << e.first << " " << e.second << "\n";
        }

        // 写入输出
        solve(N, edges, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done! All files generated." << endl;
    return 0;
}