笔记

没有什么好记的

Luogu P5318 【深基18.例3】查找文献

这是一道模板题，不过由于这道题非常的阴，如果你样例全过，评测全WA，那么大概就是没有排序的缘故

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
vector<int>tu[N];
bool vis[N];
void dfs(int x){
    if(vis[x]){
        return;
    }
    vis[x] = true;
    printf("%d ",x);
    for(int g:tu[x]){
        dfs(g);
    }
}
void bfs(){
    memset(vis,false,sizeof vis);
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now] = true;
        printf("%d ",now);
        for(int g:tu[now]){
            q.push(g);
        }
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tu[u].push_back(v);
    }
    for(int i = 1;i <= n;i++){
        sort(tu[i].begin(),tu[i].end());
    }
    dfs(1);
    printf("\n");
    bfs();
    return 0;
}

Luogu B3862 图的遍历（简单版）

这和上面那题一样模板，不想多说，大暴力就可以过

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3+10;
vector<int>tu[N];
bool vis[N];
int dfs(int x){
    if(vis[x]){
        return 0;
    }
    vis[x] = true;
    int ret = x;
    for(int g:tu[x]){
        ret = max(ret,dfs(g));
    }
    return ret;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tu[u].push_back(v);
    }
    for(int i = 1;i <= n;i++){
        memset(vis,0,sizeof vis);
        printf("%d ",dfs(i));
    }
    return 0;
}

Luogu P3916 图的遍历

我本来是想用弱化版的代码加记忆化，但似乎不行（40 pts, WA)，于是，我问了deepseek，找到了思路（只看了思路)，可以逆存储，并倒序遍历

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
vector<int>tu[N];
int ans[N];
void dfs(int x,int y){
    if(ans[x] != 0){
        return;
    }
    ans[x] = y;
    for(int g:tu[x]){
        dfs(g,y);
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tu[v].push_back(u);
    }
    for(int i = n;i >= 1;i--){
        if(ans[i] == 0){
            dfs(i,i);
        }
    }
    for(int i = 1;i <= n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

Luogu P1656 炸铁路

Tarjan没学好，这题也是等后续来扫尾

Luogu P2853 [USACO06DEC] Cow Picnic S

看了这篇题解，只看了思路

我们可以从每个有牛的牧场（或每头牛所在的牧场)开始遍历，对于一个可供进食的牧场，就走了有牛牧场的总数（或$k$)次，那么就很明显了

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
// 我为什么要开set啊，我是不是闲的
set<int>st;
int cnt[N];
vector<int>tu[N];
bool vis[N];
void dfs(int x){
    if(vis[x]){
        return;
    }
    vis[x] = true;
    cnt[x]++;
    for(int g:tu[x]){
        dfs(g);
    }
}

int main(){
    int k,n,m;
    scanf("%d%d%d",&k,&n,&m);
    for(int i = 1;i <= k;i++){
        int c;
        scanf("%d",&c);
        st.insert(c);
    }
    for(int i = 1;i <= m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tu[u].push_back(v);
    }
    for(set<int>::iterator i = st.begin();i != st.end();i++){
        memset(vis,0,sizeof vis);
        dfs(*i);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += (cnt[i]==st.size());
    }
    printf("%d",ans);
    return 0;
}