笔记

以下动画来自deepseek

Luogu B3643 图的存储

这题有点模板了，但还有警示一下，如果你样例全过，但过评测机的时候就全WA，请看看邻接表输出的要求

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
bool a[N][N];
vector<int>tu[N];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        a[u][v] = true;
        a[v][u] = true;
        tu[u].push_back(v);
        tu[v].push_back(u);
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    for(int i = 1;i <= n;i++){
        cout << tu[i].size() << " ";
        sort(tu[i].begin(),tu[i].end());
        for(int g:tu[i]){
            cout << g << " ";
        }
        cout << "\n";
    }
    return 0;
}

Luogu B3613 图的存储与出边的排序

这题也是一道比较简单的题目

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5+10;
vector<int>tu[N];

int main(){
    // freopen("1.in","r",stdin);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= m;i++){
            int u,v;
            cin >> u >> v;
            tu[u].push_back(v);
        }
        for(int i = 1;i <= n;i++){
            sort(tu[i].begin(),tu[i].end());
            for(int g:tu[i]){
                cout << g << " ";
            }
            cout << "\n";
            tu[i].clear();
        }
    }
    return 0;
}

Luogu B3852 出边排序 2

其实还挺简单的，如果你TLE 80 pts（使用 memeset重置w的值），可以尝试不修改w的值（输入时会覆盖掉）或使用for循环修改w的值

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5+10;
vector<int>tu[N];
int w[N];
bool cmp(int x,int y){
    if(w[x] != w[y]){
        return w[x]<w[y];
    }
    return x<y;
}

int main(){
    // freopen("1.in","r",stdin);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++){
            cin >> w[i];
        }
        for(int i = 1;i <= m;i++){
            int u,v;
            cin >> u >> v;
            tu[u].push_back(v);
        }
        for(int i = 1;i <= n;i++){
            stable_sort(tu[i].begin(),tu[i].end(),cmp);
            for(int g:tu[i]){
                cout << g << " ";
            }
            cout << "\n";
            tu[i].clear();
        }
    }
    return 0;
}