ABC 454 C - Straw Millionaire 题解

30分钟差点就A三道了没重构出来

solve

• 写题解表示红温
• 观察题目，发现呈A->B，所以直接掏出链式前向星建边
• 搜就完了
• 贴两份我15写的抽象代码

Code_AC

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m,ans;
int h[maxn],to[maxn],nxt[maxn],tot;
void add(int x,int y)
{tot++;to[tot]=y;nxt[tot]=h[x];h[x]=tot;
}
bool v[maxn];
void dfs(int x)
{if (v[x]) return;v[x]=1;for (int i=h[x];i;i=nxt[i]){int y=to[i];if (!v[y]) dfs(y);}return ;
}
int main()
{cin >> n >> m;for (int i=1;i<=m;i++){int x,y;cin >> x >> y;add(x,y);}dfs(1);for (int i=1;i<=n;i++) if (v[i]) ans++;cout << ans << endl;return 0;
}

Code_TLE/MLE

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m;
int h[maxn],to[maxn],nxt[maxn],tot;
void add(int x,int y)
{tot++;to[tot]=y;nxt[tot]=h[x];h[x]=tot;
}
bool v[maxn];
void dfs(int x)
{for (int i=h[x];i;i=nxt[i]){int y=to[i];if (!v[y]) dfs(y);v[y]=1;}return ;
}
int main()
{cin >> n >> m;for (int i=1;i<=m;i++){int x,y;cin >> x >> y;add(x,y);}dfs(1);int ans=1;for (int i=1;i<=n;i++) if (v[i]) ans++;cout << ans;return 0;
}

• 亖因：递归后标记

Code_WA

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m;
struct node
{int a,b;
}e[maxn];
bool cmp(node nd1,node nd2)
{return nd1.a<nd2.a;
}
bool v[maxn];
int main()
{cin >> n >> m;for (int i=1;i<=m;i++) cin >> e[i].a >> e[i].b;sort(e+1,e+1+m,cmp);v[1]=1;for (int i=1;i<=m;i++){if (v[e[i].a]) v[e[i].b]=1;}int ans=0;for (int i=1;i<=n;i++){if (v[i]) ans++;}cout << ans << endl;return 0;
}

• 亖因：诡异代码