并查集总结

这个周主要是并查集和拓扑排序的学习，并查集就是将某些元素组合到一起然后进行一些操作。

拓扑排序就像盖楼一样，首先要先盖第一层，然后才能再盖第二层，也就是盖第二层前必须要先盖第二层，就是有些操作必须在某些操作完成后才能进行的适合拓扑排序。

并查集的概念很简单，无非就是谁是谁的祖先，然后建立一棵同一祖先的树，便于查询和操作，但在题目中并查集一般就是题目中的一部分。还有就是并查集中只有并字，也就是说并查集只能将集合合并，并不能将集合拆开。

说到这，这周有两个比赛应该涉及到了并查集（我感觉），

第一个就是（因为某一地方将j写成了i所以，还能运行并且测试用例过了一点，一直没找到错误，规定时间内没做出来）

Problem - D - Codeforces

这个题大体意思就是给你一颗树，问你有几天路径（每个点出现一次），每条路径有几个根，分别是什么。下面试我的代码

#include
using namespace std; vector s; int a[200010]={0},fa[200010],b[200010]={0};

int main(){
    int t;
    cin>>t;
    while(t--){
       memset(a,0,sizeof(a));
       memset(b,0,sizeof(b));
int n,anss=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            fa[i]=x;b[x]=1;
        }
        for(int i=1;i<=n;i++){
            if(!b[i]){
                anss++;
                }
            else continue;
        }if(n==1) anss=1;
       cout<=0;i--){
                cout< 
思路就是先将树给建立起来，如果一个数没有做为别人的父亲，呢么这个数就是一条路径的结尾，有多少个这样的书，就有多少路径。然后我们对没有儿子的根进行访问，寻找其父亲并记录和标记其访问过，再就是对1进行特判。他给定的时间是两秒，我的时间有1800多毫秒，接近超时。。。
 
下面是官方正解（374毫秒）
 
#include
using namespace std;

void solve(){
    int n;
    cin >> n;
    vectorb(n + 1);
    vectorleaf(n + 1, true);
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
        leaf[b[i]] = false;
    }

    if(n == 1){
        cout << "1n1n1nn";
        return;
    }

    vectorpaths[n + 1];
    vectorused(n + 1, false);
    int color = 0;

    for(int i = 1; i <= n; i++){
        if(!leaf[i]) continue;
        used[i] = true;
        paths[color].emplace_back(i);

        int v = i;
        while (b[v] != v && !used[b[v]]){
            v = b[v];
            used[v] = true;
            paths[color].emplace_back(v);
        }
        color++;
    }

    cout << color << 'n';
    for(auto &path : paths){
        if(path.empty()) continue;
        cout << (int)path.size() << 'n';
        reverse(path.begin(), path.end());
        for(auto &v: path) cout << v << ' ';
        cout << 'n';
    }
    cout << 'n';
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}
 
第二个提就是今天参加的一个比赛中的，没有做出来，只是有一点思路，
 
G-多吃蘑菇_第20届上海大学程序设计联赛春季赛（同步赛） (nowcoder.com)
 
提议就是你到每个节点吃的蘑菇的最大值，同一颜色只能吃一次，
 
我的思路就是以1为祖宗建立一个并查集，将他输入的边小号作为父亲，想询问第几结点我们只要从他往祖宗寻找并累加就可以了，但后来我想如果他给的路径某小号和一之间有一个大号的话，呢我这个思路实现起来就会出现错误了。
 
然后结束后看了以下别人的代码，深搜！！！！而且很是简单，属实没想到，感觉前面搜索学的很是一般啊。。。。
 
拓扑排序呢看的就要比并查集少了，这两个光看算法是比较简单的，但实际用处确实比较大的。接下来就要开始做这一部分的题目了。