AJ's Algorithm Note: July 2020

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 : ABCPATH Solution

Problem : Please find the problem here

Summary : Simple DFS traversal.

Code :

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

const int mxN = 1e3, di[8]={-1, -1, -1, 0, 0, 1, 1, 1}, dj[8]={-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
string s[mxN];
int dp[mxN][mxN];


bool isok(int i, int j){
	return i>=0&&i<n&&j>=0&&j<m;
}

int dfs(int i, int j, char letter){
	if(dp[i][j] != -1)
		return dp[i][j];
	int cnt = 1;
	for(int k = 0; k < 8; k++){
		int ni = i+di[k], nj = j+dj[k];
		if(isok(ni, nj) && letter == s[ni][nj]){
			cnt = max(cnt, 1+dfs(ni, nj, letter+1));
		}
	}
	dp[i][j] = cnt;
	return cnt;
}

int main()
{
	int __case = 1;
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0){
			break;
		}
		for(int i = 0; i < n; i++){
			cin >> s[i];	
		}
		memset(dp, -1, sizeof(dp));
		int mx = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(isok(i, j) && s[i][j] == 'A'){
					mx = max(dfs(i, j, s[i][j]+1), mx);
				}
			}
		}

		cout << "Case " << __case << ": " << mx<< '\n';
		__case++;
	}
	return 0;
}

SPOJ : LastShot Solution

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

const int mxN=1e4;
int n, m, ans, cnt;
vector<int> adj[mxN];
bool vis[mxN];

void dfs(int u){
	cnt++;
	vis[u] = 1;
	//cout << u << ' ';
	for(int v : adj[u]){
		if(!vis[v]){
			dfs(v);
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 0, a, b; i < m; i++){
		cin >> a >> b;
		a--, b--;
		adj[a].emplace_back(b);
	}
	
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			cnt = 0;
			memset(vis, false, sizeof(vis));
			dfs(i);
			ans = max(cnt, ans);
		}
	}
	cout << ans;
	return 0;
}

SPOJ : Highways Solution

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

#define ll long long

const int mxN = 1e5+5;
ll n, m, d[mxN], s, e;
vector<array<ll, 2>> adj[mxN];
bool vis[mxN];

int main()
{
	int t;
	cin >> t;
	while(t--){
		cin >> n >> m >> s >> e;
		s--, e--;
		for(int i = 0; i < n; i++){
			adj[i].clear();
			d[i] = mxN;
			vis[i] = 0;
		}
		for(int i = 0, a, b, c; i < m; i++){
			cin >> a >> b >> c;
			a--, b--;
			adj[a].push_back({c, b});
			adj[b].push_back({c, a});
		}
		d[s] = 0;
		priority_queue<array<ll, 2>> pq;
		pq.push({0, s});
		while(!pq.empty()){
			array<ll, 2> u = pq.top();
			pq.pop();
			if(vis[u[1]])continue;
			vis[u[1]] = 1;
			for(array<ll, 2> v : adj[u[1]]){
				if(d[v[1]] > d[u[1]]+v[0]){
					d[v[1]] = d[u[1]]+v[0];
					pq.push({-d[v[1]], v[1]});
				}
			}
		}
		if(d[e] == mxN){
			cout << "NONE\n";
		}else{
			cout << d[e] << '\n';
		}
	}
	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;
}

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;
}

Friday, July 31, 2020