Код TLE завершается за 2,1 секунды. Я также передаю много вещей через ссылку, но все равно выдает TLE. Почему этот код занимает так много времени?
Вот проблема на hackerearth:
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
Домино очень весело. Детям нравится ставить плитки на боку в длинных очередях. Когда одно домино падает, оно сбивает с ног следующее, которое сбивает одно после этого, полностью вниз по линии. Однако, иногда домино не может сбить следующего. В этом случае мы должны сбить его с руки, чтобы домино снова упало. Ваша задача состоит в том, чтобы определить, учитывая расположение некоторых плиток домино, минимальное количество домино, которое нужно сбить рукой, чтобы все домино упали.
Ввод
Первая строка ввода содержит одно целое число, указывающее количество тестовых примеров, которым необходимо следовать. Каждый тестовый пример начинается со строки, содержащей два целых числа, каждое из которых не превышает 100 000. Первое целое число n - это число плиток домино, а второе целое число m - количество строк, которые должны следовать в тестовом примере. Плитки домино пронумерованы от 1 до n. Каждая из следующих строк содержит два целых числа x и y, указывающих, что если число домино x упадет, это также приведет к падению числа домино y.
Выход
Для каждого теста выведите a строка, содержащая одно целое число, минимальное количество домино, которое нужно опрокинуть вручную, чтобы все домино упали.
SAMPLE INPUT 1 3 2 1 2 2 3 SAMPLE OUTPUT 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 сек c.
#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;
}