Code throws TLE

#1

CodeLink->https://ide.codingblocks.com/s/285489
I also have considered the all edges not in a single component but don’t know where it wrong.

#2

Vectors are supposed to be passed by reference.

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define int long long
#define pb push_back
#define pback pop_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define vis vector<string>
#define vii vector<vector<int>>
#define mii map<int, int>
#define umii unordered_map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi,greater<int>>
#define setbits(x) __buitin_popcountll(x)
#define zrobits(x) __buitln_ctzll(x)
#define mod 1000000007 //1e9+7
#define inf 1e18
#define ps(x,y) fixed<<setpresicion(y)<<x
#define mk(arr,n,type) type *arr=new type[n]
#define w(x) int x;cin>>x; while(x--)
#define rg 1000005
#define deg(v) cout<<"Value is: "<<v<<endl
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define f(a,b) for(int i=a;i<b;i++)
#define frev(a,b) for(int i=(int)a;i>(int)b;--i)
//mt19937  ring(chrono: stready_clock::now().time_since_epoch().count)


void IO() {


#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

void dfs(vii& g, int curr, bool *visited, int *par, int *child, int &count) {


	visited[curr] = true;

	for (auto X : g[curr]) {

		if (!visited[X]) {
			dfs(g, X, visited, par, child, count);
			par[X] = curr;
			child[curr]++;

			if (child[X] > child[par[X]]) count++;
		}
	}

}

int32_t main() {

	FASTIO;
	//IO();
	int n, m; cin >> n >> m;

	vii g(n + 1);

	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;

		g[x].pb(y);
		g[y].pb(x);
	}

	int *child = new int[n + 1];
	int *par = new int[n + 1];
	bool *visited = new bool[n + 1];
	for (int i = 0; i < n + 1; i++)  child[i] = par[i] = visited[i] = 0;

	int count = 0;

	for (int i = 1; i <= n; i++) {

		if (!visited[i]) {
			dfs(g, i, visited, par, child, count);

		}
	}

	cout << count << endl;
	return 0;
}
#3

hi @Madeshi-Chinmay-2159857244260221 when i was submitted that above code then it won’t accepted.

#4

Now is it showing tle or wa ?

#5

@Madeshi-Chinmay-2159857244260221 it shows WA

#6

What I would suggest you here is that don’t count the beautiful vertices during the dfs … just calculate that child count for every node in that child array and then do another dfs to check if now the count of any child is greater than its parent.

It might be a safer option as per me .

#7

Or what you can do is rather than doing child[parent[X]] just write the size of the list of nodes of parent because all those nodes are the children of the parent .