CSES :: Tree Algorithms :: Subordinates

Problem : Please find the problem here.

Explanation : Company's employee hierarchy can be intutively mapped as tree structure and for each employee, the subordinate count is the sum of subordinates count of all their direct subordinates.

Code : Used DFS to traverse the tree starting from the node 0. This calculates the subordinates for each employee by summing counts recursively.

Time Complexity : O(N), where n is the number of nodes in the tree.

#include <bits/stdc++.h>

using namespace std;

void DFS(int node, int parent, vector<int> &subordinates, vector<vector<int>> &adj) {
    subordinates[node] = 1;

    for (int next : adj[node]) {
        DFS(next, node, subordinates, adj);
        subordinates[node] += subordinates[next];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> subordinates(n);

    // relation data for employee 1 to n; 0th is boss.
    for (int i = 1; i < n; i++) {
        cin >> x; x--;
        adj[x].emplace_back(i);
    }

    DFS(0, -1, subordinates, adj);

    for (int c : subordinates) {
        cout << c-1 << ' ';
    }
    return 0;
}

UVa : 1357 :: Cells

Problem : Please find the problem here.

Summary : This can be solved using DFS. Considering the relation between the order in which a node and its ancestors are visited, we can set the in-time and out-time for each node in DFS when entering and leaving the node. Now a node u will be an ancestor of node v if and only if the in-time of u is less than the in-time of v and out-time of u is greater than the out-time of v.

Code : The key thing for me to learn in this problem was to store the first child of every node, and during DFS iterate from this first child to (first_child + total_child). My previous solution was correct but was giving TLE verdict, then after I discoverd this trick to only store the first child for the given node.

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

const int mxN = 3e5, mxM = 2e7;
int n, m, c[mxN], b[mxN], tin[mxM], tout[mxM], cnt;
vector<int> adj[mxN];
bool vis[mxM];

void dfs(int u){
	tin[u] = cnt++;
	for(int v = b[u]; v < c[u]+b[u]; v++){
		if(v >= n){
			tin[v] = cnt++;
			tout[v] = cnt++;
		}
		else{
			dfs(v);
		}
	}
	tout[u] = cnt++;
}

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> c[i];
		if(i == 0) b[i] = 1;
		else b[i] = b[i-1]+c[i-1];
	}
	/*
	for(int i = 0; i < n; i++){
		cout << b[i] << ' ';
	}
	cout << '\n';
	*/
	cnt = 0;
	memset(tin, 0, sizeof(tin));
	memset(tout, 0, sizeof(tout));
	dfs(0);
	cin >> m;
	for(int i = 0, u, v; i < m; i++){
		cin >> u >> v;
		cout << ((tin[u]<tin[v] && tout[v]<tout[u])?"Yes\n":"No\n");
	}
}
int main()
{
	int t;
	cin >> t;
	for(int k = 1; k <= t; k++){
		if(k != 1){
			cout << "\n";
		}
		cout << "Case " << k << ":\n";
		solve();
	}	
	return 0;
}

SPOj : Is It Tree Solution

Problem : Please find the problem here.

Summary : To check if the given graph is a tree, we need to make sure that the graph is acyclic and connected with exactly one connected component.

Code :

#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 1e5;
int n, m, p[mxN];
vector<int> adj[mxN];
bool vis[mxN];
 
void dfs(int u, int pu=-1){
	vis[u]=true;
	p[u] = pu;
	for(int v : adj[u]){
		if(pu == v){
			continue;
		}
		if(vis[v]){
			cout << "NO";
			exit(0);
		}
		else{
			dfs(v, u);
		}
	}
}
 
int main()
{
	cin >> n >> m;
	for(int i = 0,a ,b; i < m; i++){
		cin >> a >> b, a--, b--;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}	
	int cnt =0;
	memset(vis, false, sizeof(vis));
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			//cout << vis[i] << ' ';
			dfs(i);
			cnt++;
		}
	}
	if(cnt == 1){
		cout << "YES";
	}
	return 0;
}

SPOJ : Bugs Life Solution

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

const int mxN = 2e5;
vector<int> adj[mxN];
int n, m, c[mxN];

bool isBipartite(int u){
	bool res = 1;
	for(int v : adj[u]){
		if(c[v] != 0){
			if(c[v] == c[u]){
				return false;
			}
		}
		else{
			c[v] = -c[u];
			res &= isBipartite(v);
		}
	}
	return res;
}

int main()
{
	int t;
	cin >> t;
	for(int k = 1; k <= t; k++){
		cin >> n >> m;
		for(int i = 0; i < n; i++){
			c[i] = 0;
			adj[i].clear();
		}
		for(int i = 0, a, b; i < m; i++){
			cin >> a >> b, a--, b--;
			adj[a].emplace_back(b);
			adj[b].emplace_back(a);
		}
		
		bool ok = 1;
		for(int i = 0; i < n; i++){
			if(c[i] == 0){
				c[i] = 1;
				ok &= isBipartite(i);
			}
		}
		cout << "Scenario #" << k << ":\n";
		if(ok){
			cout << "No suspicious bugs found!";
		}else{
			cout << "Suspicious bugs found!";
		}
		cout << '\n';
	}
	return 0;
}