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 : Inversion Count (INVCNT) Solution [Using Merge-Sort]

Time Complexity : O(nlogn)

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

ll merge(vector<int> &arr, vector<int> &tmp, int L, int M, int R){
	int i = L, j = M+1, k = L;
	ll cnt = 0;
	while(i <= M && j <= R){
		if(arr[i] <= arr[j]){
			tmp[k++] = arr[i++];
		}
		else{
			tmp[k++] = arr[j++];
			cnt += (M-i+1);
		}
	}
	while(i <= M){
		tmp[k++] = arr[i++];
	}
	for(int i = L; i <= R; i++){
		arr[i] = tmp[i];
	}
	return cnt;
}

ll merge_sort(vector<int>&arr, vector<int> &tmp, int L, int R){
	if(L == R) return 0;
	int M = L +(R-L)/2;
	cnt += merge_sort(arr, tmp, L, M);
	cnt += merge_sort(arr, tmp, M+1, R);
	cnt += merge(arr, tmp, L, M, R);
	return cnt;
}

int main()
{
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<int> arr(n), tmp(n);
		for(int i = 0; i < n; i++){
			cin >> arr[i];
			tmp[i] = arr[i];
		}
		cout << merge_sort(arr, tmp, 0, n-1) << '\n';
	}
	return 0;
}