TLE 代码在 2.1 秒内完成。我也通过参考传递了很多东西，但它仍然抛出一个 TLE。为什么这段代码需要这么多时间？
这是hackerearth的问题：
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
多米诺骨牌很有趣。孩子们喜欢把瓷砖竖着排成一长队。当一张多米诺骨牌倒下时，它会撞倒下一张，然后再撞倒另一张，一直向下。然而，有时一张多米诺骨牌无法击倒下一张。在这种情况下，我们必须用手将其击倒以使多米诺骨牌再次倒下。你的任务是根据一些多米诺骨牌的布局确定必须用手击倒的骨牌的最小数量才能使所有骨牌倒下。
输入
输入的第一行包含一个整数，指定要遵循的测试用例的数量。每个测试用例都以包含两个整数的行开始，每个整数不大于 100 000。第一个整数 n 是多米诺骨牌的数量，第二个整数 m 是测试用例中要遵循的行数。多米诺牌从 1 到 n 编号。以下每一行都包含两个整数 x 和 y，表示如果 domino 编号 x 下降，它将导致 domino 编号 y 也下降。
输出
对于每个测试用例，输出一行，其中包含一个整数，即为使所有多米诺骨牌倒下而必须用手打倒的最少骨牌数量。
样品输入 1 3 2 1 2 2 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;
}