Department Strengths /cant find editorial/wrong answer

CodeChef-DSA-learners
1

I am getting wrong answer in some test cases in the question this
problem. Also can’t find the editorial in practise section either.

my solution is here

2

See this

If above link is broken 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define tc int t;cin>>t;while(t--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff(i,a,b) for(i=a;i<b;i++)
#define fb(i,b,a) for(i=b;i>a;i--)
#define ffi(i,a,b,c) for(i=a;i<b;i+=c)
#define fbi(i,b,a,c) for(i=b;i>a;i-=c)
#define clin(s) getline(cin,s)
#define MOD 1e9+7
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound
int m,n;
vector<vector<int>> adj;
vector<vector<int>> deps;
int visited[100001];
int uc=0;//global counter
void explore(int r){
    visited[r]=1;
    int i;
    ff(i,0,adj[r].size()){
        if(!visited[adj[r][i]]){
            deps[uc].pb(adj[r][i]);
            explore(adj[r][i]);
        }
    }
}
void sdeps(){
    int i;
    ff(i,0,n){
        if(!visited[i]){
            deps.pb({i});
            explore(i);
            uc+=1;
        }
    }
}
ll gdlfr(int root, int parent, int depth){
	if(adj[root].size()==0)return depth;
	ll level=depth;
	int i;
	ff(i,0,adj[root].size()){
		if(adj[root][i]!=parent)
		    level += gdlfr(adj[root][i],root,depth+1);
	}
	//cout<<level<<"\n";
	return level;
}
void solve(){
	cin>>n>>m;
	int i,j;
	adj.resize(n);
	ff(i,0,m){
		int u,v;
		cin>>u>>v,u--,v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	sdeps();
	ull odd=0,even=0;
	ff(i,0,deps.size()){
		if(deps[i].size()%2==0){
			//Type Even
			int root = *min_element(all(deps[i]));
			//cout<<"EVEN:"<<root<<"\n";
			even+=gdlfr(root,-1,1);
		} else {
			//Type Odd
			int root = *max_element(all(deps[i]));
			//cout<<"ODD:"<<root<<"\n";
			odd+=gdlfr(root,-1,1);
		}
	}
	cout<<even<<" "<<odd<<"\n";
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	tc {
		adj.clear();
		deps.clear();
		fill(visited,visited+100001,0);
		uc=0;
		solve();
	}
}

sdeps() seperates the departments
gdlfr() stands for Get Department level from root

  1. Seperate the departments

  2. Calculate levels according to department sizes(even/odd). Since each connected component in this graph is undirected and non-cyclic, so here, i use one more parameter parent instead of one more visited[] for gdlfr() , we just need to care about the parent, so that we don’t traverse back in the graph.

Hope, it helps :slightly_smiling_face:
(Btw, your solution link returns 403)