Acw 836 合并集合

题目

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

题解

1. 把数看作图的结点，M操作就是把结点连接起来，Q就是求a b是否在图的同一个连通分量中。

    // 构造图
    unordered_map<int, vector<int>> tree;
    if (ins == 'M') {
        auto iter = find(tree[a].begin(),tree[a].end(),b);
        if (iter == tree[a].end() ) {
            tree[a].push_back(b);			// 构造无向图，存两条边
            tree[b].push_back(a);			// 此题需要构造无向图，否则的话从a不一定能搜索到b
        }
    } 
        
    // 遍历图，看是否在同一个连通分量中
    // BFS - BFS递归栈可能很深，导致内存爆掉
    // Memory Limit Exceeded   
    void bfs(int a, int father, int b)
    {
        if (a == b) {
            found = true;
            return;
        }
        for(auto n : tree[a]) {
            if (n == father) continue;
            bfs(n, a, b);
        }
    }
    // DFS - 同样很慢，数据量太大时会超时
    bool dfs(int a, int f, int b)
    {
        queue<int> q;					// 辅助队列
        unordered_map<int, int> father;		// 记录遍历时的父结点
        unordered_map<int, bool> visited;	// 记录结点是否访问过
            
        father[a] = f;
        q.push(a);
        visited[a] = false;
            
        while (q.empty() == false) {
                
            int root = q.front();       // front取队头元素
            if (root == b) {
                return true;
            }
            visited[root] = true;
            q.pop();            // pop 弹出队头元素
        
            for(auto n : tree[root]) {
                if (n == father[root]) continue;
                if (visited[n] == true) continue;
                father[n] = root;
                q.push(n);
                visited[n] = false;
            }
        }