TLE代码以2.1秒完成。我也通过参考传递了很多东西，但它仍然抛出了一个TLE。为什么这个代码要花这么多时间？
这是hackerearth的问题：
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
多明尼奥斯很有趣。孩子们喜欢把瓷砖放在一边排成长队。当一块多米诺骨牌倒下时，它会击倒下一块，然后再击倒下一张，一直到最后。然而，有时多米诺骨牌无法击倒下一张。在这种情况下，我们必须用手把它推倒，才能让多米诺骨牌再次倒下。你的任务是，考虑到一些多米诺骨牌瓷砖的布局，确定必须用手推倒的多米诺骨牌的最小数量，才能让所有多米诺骨牌倒下。
输入
第一行输入包含一个整数，指定要遵循的测试用例的数量。每个测试用例以一行开始，该行包含两个整数，每个整数不大于100000。第一个整数n是domino瓦片的数量，第二个整数m是测试用例中要遵循的行数。多米诺骨牌的编号从1到n。下面的每一行都包含两个整数x和y，表示如果多米诺骨牌数量x下降，也会导致多米诺骨牌数字y下降。
输出
对于每个测试用例，输出一行，其中包含一个整数，这是为了让所有多米诺骨牌掉落，必须用手敲击的多米诺骨牌的最小数量。
样本输入1.3 21 22 3样本输出1
代码在2.1完成
#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
using namespace std;
void dfs(const vector<vector<int>> &edges, unordered_set<int> &visited,int sv, stack<int> &stk){
visited.insert(sv);
for(int i=0;i<edges[sv].size();i++){
int current = edges[sv][i];
if(visited.find(current)==visited.end())
dfs(edges, visited, current, stk);
}
stk.push(sv);
}
void dfs(const vector<vector<int>> &edges, unordered_set<int> &visited,int sv){
visited.insert(sv);
for(int i=0;i<edges[sv].size();i++){
int current = edges[sv][i];
if(visited.find(current)==visited.end())
dfs(edges, visited, current);
}
}
int main()
{
int t;
cin>>t;
while(t--){
int V, E;
cin>>V>>E;
vector<vector<int>> edges(V+1);
unordered_set<int> visited;
stack<int> stk;
while(E--){
int f, s;
cin>>f>>s;
edges[f].push_back(s);
}
for(int i=1;i<=V;i++)
if(visited.find(i)==visited.end())
dfs(edges, visited, i, stk);
visited.clear();
int count{0};
while(!stk.empty()){
int current = stk.top();
stk.pop();
if(visited.find(current)==visited.end()){
dfs(edges, visited, current);
count++;
}
}
cout<<count<<endl;
}
return 0;
}
高效代码在0.7秒内完成。
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void dfs( vector<int> *edges , int start,int n,bool *visit ,stack<int> *nodex)
{
visit[start] = true;
// cout<<start<<endl;
for (int i = 0; i < edges[start].size(); ++i)
{
int next = edges[start][i];
if(visit[next] == false)
dfs(edges,next,n,visit,nodex);
}
nodex->push(start);
}
void dfs(vector<int> *edges,int start, bool *visit,int n)
{
visit[start] = true;
for(int i=0;i<edges[start].size();i++)
{
int next = edges[start][i];
if(visit[next]==false)
dfs(edges,next,visit,n);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<int> *edges = new vector<int>[n+1];
for (int i = 0; i < m; ++i)
{
int start,end;
cin>>start>>end;
edges[start].push_back(end);
}
// cout<<"PHASE 1"<<endl;
bool *visit = new bool[n+1];
for (int i = 0; i<=n; ++i)
{
visit[i] = false;
}
stack<int> *nodex = new stack<int>();
for (int i = 1; i<=n; ++i)
{
if(visit[i] == false)
dfs(edges,i,n,visit,nodex);
}
// cout<<"PHASE 2"<<endl;
for(int i=0;i<=n;i++)
visit[i] = false;
int count=0;
while(!nodex->empty())
{
int up = nodex->top();
nodex->pop();
// cout<<" EVERYTHING ISS FINE "<<up<<endl;
if(visit[up] ==false )
{
dfs(edges,up,visit,n);
count++;
}
// cout<<"Everrything is fine "<<up<<endl;
}
cout<<count<<endl;
}
return 0;
}
使用快速I/O和"\n〃；代替endl。这对消除TLE有很大帮助。对我来说，代码的其余部分似乎很好