TLE code completes at 2.1 secs. I'm also passing many things through reference but it's still throwing a TLE. Why this code takes so much time?
here is the problem at hackerearth:
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again. Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.
Input
The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.
Output
For each test case, output a line containing one integer, the minimum number of dominos that must be knocked over by hand in order for all the dominos to fall.
SAMPLE INPUT 1 3 2 1 2 2 3 SAMPLE OUTPUT 1
code completes at 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 completes at 0.7 sec.
#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;
}
Use Fast I/O and "\n"in place of endl. This helps a lot in getting rid of TLE. For me the rest of the code seems to be fine