UVa : 10926 :: How Many Dependencies?

Problem : Please find the problem here.

Explanation : We are basically asked to find a node with highest degree or find a connected component with highest number of nodes and print any one node from it. 

Code : Used DFS.

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

const int mxN = 100;
int t, n, m, cnt;
vector<int> adj[mxN];
bool vis[mxN];

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

void init(){
	for(int i = 0; i < n; i++){
		adj[i].clear();
	}
	cnt = 0;
	memset(vis, 0, sizeof(vis));
}

int main()
{
	while(cin >> n && n){
		init();
		for(int i = 0, u, v; i < n; i++){
			cin >> u;
			for(int j = 0; j < u; j++){
				cin >> v, v--;
				adj[i].emplace_back(v);
			}
		}
		int index = INT_MAX;
		int d = -1;
		for(int i = 0; i < n; i++){
			memset(vis, 0, sizeof(vis));
			cnt = 0;
			dfs(i);
			if(cnt > d){
				d = cnt;
				index = i;
			}else if(cnt == d){
				index = min(i, index);
			}	
		}
		cout << index+1 << '\n';
	}	
	return 0;
}
	

UVa : 11518 :: Dominos 2

Problem : Please find the problem here.

Explanation : simply count the connected components. Also checkout UVa-11504-Dominos. 

Code : Used DFS.

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

const int mxN = 100, di[8]={1, 0, -1, 0, -1, -1, 1, 1}, dj[8]={0, 1, 0, -1, -1, 1, -1, 1};
int n, m, ans;
vector<int> disjoint_sets(10000);
string s[mxN], in;
bool vis[mxN][mxN];


bool isok(int i, int j){
	return i>=0 && i<n && j>=0 && j<m && s[i][j]=='W' && !vis[i][j]; 
}

void dfs(int i, int j){
	vis[i][j] = 1;
	for(int k = 0; k < 8; k++){
		int ni = i + di[k], nj = j + dj[k];
		if(isok(ni, nj)){
			dfs(ni, nj);
		}
	}
	ans++;
}

int main()
{
	int t;
	cin >> t;
	getline(cin, in);
	getline(cin, in);
	for(int c = 0; c < t; c++){
		getline(cin, in); 
		int k = 0;
		while(1){
			if(in.length() == 0 || (in[0] != 'L' && in[0] !='W')){
				break;
			}
			s[k++] = in;
			getline(cin, in);
		}
		n = k, m = s[0].length();
		memset(vis, false, sizeof(vis));
		if(c != 0){
			cout << '\n';
		}
		while(1){
			stringstream ss(in);
			int u, v;
			ss >> u;
		    ss >> v;
			u--, v--;
			ans = 0;
			memset(vis, 0, sizeof(vis));
			dfs(u, v);
			cout << ans << '\n';	
			if(cin.eof()){
				break;
			}
			getline(cin, in);
			if(in.length() == 0){
				break;
			}
		}
	}	
	return 0;
}

UVa : 469 :: Wetlands of Florida

Problem : Please find the problem here.

Explanation : The Problem basically asks to count the number of connected components in the grid, similiar to the problem Graph connectivity, once again the input format was annoying.

Code : Used DFS.

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

const int mxN = 100, di[8]={1, 0, -1, 0, -1, -1, 1, 1}, dj[8]={0, 1, 0, -1, -1, 1, -1, 1};
int n, m, ans;
vector<int> disjoint_sets(10000);
string s[mxN], in;
bool vis[mxN][mxN];


bool isok(int i, int j){
    return i>=0 && i<n && j>=0 && j<m && s[i][j]=='W' && !vis[i][j]; 
}

void dfs(int i, int j){
    vis[i][j] = 1;
    for(int k = 0; k < 8; k++){
	int ni = i + di[k], nj = j + dj[k];
	if(isok(ni, nj)){
	    dfs(ni, nj);
	}
    }
    ans++;
}

int main()
{
    int t;
    cin >> t;
    getline(cin, in);
    getline(cin, in);
    for(int c = 0; c < t; c++){
	getline(cin, in); 
	int k = 0;
	while(1){
	    if(in.length() == 0 || (in[0] != 'L' && in[0] !='W')){
		break;
	    }
	    s[k++] = in;
	    getline(cin, in);
        }
	n = k, m = s[0].length();
	memset(vis, false, sizeof(vis));
	if(c != 0){
	    cout << '\n';
	}
	while(1){
	    stringstream ss(in);
	    int u, v;
	    ss >> u;
	    ss >> v;
	    u--, v--;
	    ans = 0;
	    memset(vis, 0, sizeof(vis));
	    dfs(u, v);
	    cout << ans << '\n';	
	    if(cin.eof()){

                break;
	    }
	    getline(cin, in);
	    if(in.length() == 0){
                break;
	    }
	}
    }	
    return 0;
}

UVa : 459 :: Graph Connectivity

Problem : Please find the problem here.

Explanation : Though the problem is easy and only asks for the number of connected components, the input parsing is tiresome and irritating. But still good for practice purpose. 

Code : Used DFS to count the number of connected components.

#include <bits/stdc++.h>
//#define debug

using namespace std;

const int mxN = 27;
string s, n;
int u, v, m;
vector<int> adj[mxN];
bool vis[mxN];

void dfs(int u){
	vis[u] = 1;
	for(int v : adj[u]){
		if(!vis[v]){
			dfs(v);
		}
	}
}

void init(){
	for(int i = 0; i < m; i++){
		adj[i].clear();
	}
	memset(vis, 0, sizeof(vis));
}

void set_values(){
	u = int(s[0]-'A');
	v = int(s[1]-'A');
#ifdef debug
	cout << u << ' ' << v << '\n';
#endif
}

int main()
{
	ofstream fout("out");
	int tt;
	cin >> tt;
	while(tt--){
		cin >> n;
		m = (int)(n[0]-'A')+1;
		init();
		getline(cin, s);
		while(1){
			getline(cin, s);
			if(s.length() == 0){
				break;
			}
			set_values();
			adj[u].emplace_back(v);
			adj[v].emplace_back(u);
		}

		int cnt = 0;
		for(int i = 0; i < m; i++){
			if(!vis[i]){
				dfs(i); cnt++;
			}
		}	
		if(tt){
			cout << cnt << "\n\n";
		}
		else{
			cout << cnt << '\n';
		}
	}
	return 0;
}

UVa : 439 :: Knight Moves

Problem : Please find the problem here.

Explanation : We are asked to find the shortest distance between the two given squares on the chess board. 

Code : Used BFS.

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

const int mxN = 9, di[8]={2, 2, 1, -1, -2, -2, -1, 1}, dj[8]={-1, 1, 2, 2, 1, -1, -2, -2};
int si, sj, ti, tj, d[mxN][mxN];
bool vis[mxN][mxN];
string s;

bool isok(int i, int j){
    return i>=1 && i<=8&& j >=1 && j<= 8 && !vis[i][j];
}

void init(){
    memset(d, 0, sizeof(d));
    memset(vis, 0, sizeof(vis));
}

void set_values(string s){
    si = (int)(s[0]-'a')+1;
    sj = (int)(s[1]-'0');

    ti = (int)(s[3]-'a')+1;
    tj = (int)(s[4]-'0');
    //cout << si << sj << ' ' << ti << tj << '\n';
}

int main()
{
    while(getline(cin, s)){
        init();
        set_values(s);
	queue<array<int, 2>> qu;
	qu.push({si, sj});
	vis[si][sj] = 1;
	d[si][sj] = 0;
	while(qu.size()){
	    array<int, 2> u = qu.front();
	    qu.pop();
	    for(int k = 0; k < 8; k++){
	        int ni = di[k]+u[0], nj= dj[k]+u[1];
		if(isok(ni, nj)){
		    qu.push({ni, nj});
		    vis[ni][nj] = 1;
		    d[ni][nj] = d[u[0]][u[1]]+1;
		}
	    }
	}
	cout << "To get from " << s[0] << s[1] <<" to " << s[3] << s[4] << " takes " << d[ti][tj] << " knight moves.\n";
    }
    return 0;
}