TLE コードは 2.1 秒で完了します。また、参照を介して多くのものを渡していますが、まだ TLE をスローしています。このコードはなぜそんなに時間がかかるのですか?
ハッカーアースの問題は次のとおりです。
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
ドミノはとても楽しいです。子供たちは、タイルを横に並べて長い列に並べるのが好きです。1 つのドミノが倒れると、次のドミノが倒され、次のドミノが最後まで倒されます。ただし、ドミノが次のドミノを倒せないことがあります。その場合、ドミノを再び落下させるには、手で倒さなければなりません。あなたの仕事は、与えられたいくつかのドミノ タイルのレイアウトから、すべてのドミノを倒すために手で倒さなければならないドミノの最小数を決定することです。
入力
入力の最初の行には、追跡するテスト ケースの数を指定する 1 つの整数が含まれます。各テスト ケースは、それぞれが 100 000 を超えない 2 つの整数を含む行で始まります。最初の整数 n はドミノ タイルの数で、2 番目の整数 m はテスト ケースで続く行の数です。ドミノ牌には 1 から n までの番号が付けられています。次の各行には、x と y の 2 つの整数が含まれており、ドミノ番号 x が倒れるとドミノ番号 y も倒れることを示しています。
出力
テスト ケースごとに、1 つの整数を含む行を出力します。これは、すべてのドミノを倒すために手で倒さなければならないドミノの最小数です。
サンプル入力 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;
}
Efficient Code は 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;
}