# WA in Department Strength(INOI2001)

I performed dfs on the graph first to get the size and the level and then calculated the strength of the graph using bfs.

https://www.codechef.com/viewsolution/39696038

Please guys help me out with it.I am not getting any test case in which it is not going to work

I donâ€™t think a BFS is required, a DFS is enough. Since I donâ€™t know Java, I canâ€™t help you with the code. But since I had solved this problem sometime back, I am posting the code in C++ for your reference (in case you know C++).

CODE
``````#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int INF = 1e9;
const int MAXN = 1e5+5;

ll scoreE = 0, scoreO = 0;
int maxV = -INF, minV = INF;

vector<int> cmpE, cmpO;
vector<int> level(MAXN,1);
vector<bool> vis(MAXN,false);

int cnt = 0;
void cmps(int u)
{
maxV = max(maxV, u), minV = min(minV, u);
vis[u] = true;
cnt++;

{
if(!vis[v])
cmps(v);
}
}

void score(int u, int x)
{
vis[u] = true;
if(!x) scoreE += (ll) level[u];
else scoreO += (ll) level[u];
{
if(!vis[v])
{
level[v] = level[u]+1;
score(v,x);
}
}
}

int main()
{
FASTIO
int t;
cin >> t;
while(t--)
{
scoreE = 0, scoreO = 0;
maxV = -INF, minV = INF;
cmpE.clear(), cmpO.clear();
level.assign(MAXN,1);
vis.assign(MAXN,false);
cnt = 0;
int n, m;
cin >> n >> m;

for(int i=0; i<m; i++)
{
int a, b;
cin >> a >> b;
}

for(int u=1; u<=n; u++)
{
maxV = -INF, minV = INF;
cnt = 0;
if(!vis[u])
{
cmps(u);
if(cnt&1) cmpO.push_back(maxV);
else cmpE.push_back(minV);
}
}

//        for(int x : cmpE) cout << x << " ";
//        cout << "\n";
//        for(int x : cmpO) cout << x << " ";
//        cout << "\n";

vis.assign(MAXN,false);
for(int u : cmpE)
score(u,0);
for(int u : cmpO)
score(u,1);
cout << scoreE << " " << scoreO << "\n";
}
return 0;
}
``````

Yes @utkarsh1729 it can be just solved by dfsâ€¦just by using an array storing the levels of each node and computing the sum.
I thought to utilize both of it .But I dont know why its giving WA