新年第一 po！

题解 #

这个题我们用并查集来合并集合并用std::list 或 std::vector来维护每个集合里面的元素。（理论上来说 list 应该快很多，但提交后的运行时间差不多）

具体步骤就是：

找到两个猫的祖先的 id
合并两个集合，并且拼接两个链表（或者数组）

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define _ <<' '<<
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) _ #y<<" = "<<y<<endl;
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=15e4+5;
int pre[N];
int find(int x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
void join(int x,int y){
    x=find(x),y=find(y);
    pre[x]=y;
}
list<int> v[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
    cin>>n;
    for1(i,n) pre[i]=i,v[i].eb(i);
    forn(i,n-1){
        int x,y;
        cin>>x>>y;
        x=find(x),y=find(y);
        v[x].splice(v[x].end(),v[y]);    
        pre[y]=x;
    }
    for(auto it:v[find(1)]) cout<<it<<' ';
    return 0;
}

Codeforces 1131F - Asya And Kittens 题解

题解 #

Code #