CareerCup

public class Rods {
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		int res;
		int n;
		n = Integer.parseInt(in.nextLine());

		int pairsCount = 0;
		pairsCount = Integer.parseInt(in.nextLine());
		String[] pairs = new String[pairsCount];
		String pair;
		for (int i = 0; i < pairsCount; i++) {
			pair = in.nextLine();
			pairs[i] = pair;
		}

		res = calcCost(n, pairs);
		System.out.println(res);
	}

	private static int calcCost(int n, String[] pairs) {
		int[] rank, parent, count;
		rank = new int[n + 1];
		parent = new int[n + 1];
		count = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
			count[i] = 1;
		}
		for (String pair : pairs) {
			String[] xy = pair.split(" ");
			int x = Integer.parseInt(xy[0]);
			int y = Integer.parseInt(xy[1]);
			union(x, y, parent, rank, count);
		}
		int res = 0;
		for (int z : count) {
			if (z > 1) {
				res += (int) Math.ceil(Math.sqrt(z));
			} else {
				res += z;
			}
		}
		return res;
	}

	private static int find(int x, int[] parent) {
		if (parent[x] != x) {
			parent[x] = find(parent[x], parent);
		}
		return parent[x];
	}

	private static void union(int x, int y, int[] parent, int[] rank,
			int[] count) {
		int xRoot = find(x, parent), yRoot = find(y, parent);
		if (xRoot == yRoot)
			return;
		if (rank[xRoot] < rank[yRoot]) {
			parent[xRoot] = yRoot;
			count[yRoot] += count[xRoot];
			count[xRoot] = 0;
		} else if (rank[yRoot] < rank[xRoot]) {
			parent[yRoot] = xRoot;
			count[xRoot] += count[yRoot];
			count[yRoot] = 0;
		} else {
			parent[yRoot] = xRoot;
			count[xRoot] += count[yRoot];
			count[yRoot] = 0;
			rank[xRoot] = rank[xRoot] + 1;
		}
	}

}

Didn't get the meaning of the question. could you explain more?

Find all connected rods using union find algorithm of disjoint set. Determine the cost accordingly.

import math


class Data(object):
    def __init__(self, name):
        self.__name = name
        self.__links = set()

    @property
    def name(self):
        return self.__name

    @property
    def links(self):
        return set(self.__links)

    def add_link(self, other):
        self.__links.add(other)
        other.__links.add(self)

        # The function to look for connected components.


def connected_components(nodes):
    # List of connected components found. The order is random.
    result = []

    # Make a copy of the set, so we can modify it.
    nodes = set(nodes)

    # Iterate while we still have nodes to process.
    while nodes:

        # Get a random node and remove it from the global set.
        n = nodes.pop()

        # This set will contain the next group of nodes connected to each other.
        group = {n}

        # Build a queue with this node in it.
        queue = [n]

        # Iterate the queue.
        # When it's empty, we finished visiting a group of connected nodes.
        while queue:
            # Consume the next item from the queue.
            n = queue.pop(0)

            # Fetch the neighbors.
            neighbors = n.links

            # Remove the neighbors we already visited.
            neighbors.difference_update(group)

            # Remove the remaining nodes from the global set.
            nodes.difference_update(neighbors)

            # Add them to the group of connected nodes.
            group.update(neighbors)

            # Add them to the queue, so we visit them in the next iterations.
            queue.extend(neighbors)

        # Add the group to the list of groups.
        result.append(group)

    # Return the list of groups.
    return result

    # The test code...


def minimalCost(n, pairs):
    nodes_map = {x: Data(x) for x in xrange(1, n + 1)}

    for pair in pairs:
        p, q = int(pair.split(' ')[0]), int(pair.split(' ')[1])
        nodes_map[p].add_link(nodes_map[q])

    # Find all the connected components.
    cost = 0
    for components in connected_components(nodes_map.values()):
        # names = sorted(node.name for node in components)
        # print names
        cost += math.ceil(math.sqrt(len(components)))
    return long(cost)

#include <bits/stdc++.h>
using namespace std;
void bfs(vector<vector<int>> &graph,vector<int> &visited,int source)
{
queue<int> q;
q.push(source);
visited[source]=source;
while(!q.empty())
{
int curr=q.front();
q.pop();
for(int i=0;i<graph[curr].size();i++)
{
if(visited[graph[curr][i]]==-1)
{
q.push(graph[curr][i]);
visited[graph[curr][i]]=source;
}
}
}
}

int main() {
int n,m;
cin>>n;
cin>>m;
vector<vector<int>> graph(n);
for(int i=0;i<m;i++)
{
int x,y;
cin>>x;
cin>>y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
int result=0;
vector<int> visited(n,-1);
for(int i=0;i<n;i++)
{
if(visited[i]==-1)
{
bfs(graph,visited,i);
int count=0;
for(int j=0;j<n;j++)
{
if(visited[j]==i)
{
count++;
}
}
result+=ceil(sqrt(count));
}
}
cout<<result<<endl;
return 0;
}

#include <bits/stdc++.h>
using namespace std;
void bfs(vector<vector<int>> &graph,vector<int> &visited,int source)
{
    queue<int> q;
    q.push(source);
    visited[source]=source;
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        for(int i=0;i<graph[curr].size();i++)
        {
            if(visited[graph[curr][i]]==-1)
            {
                q.push(graph[curr][i]);
                visited[graph[curr][i]]=source;
            }
        }
    }
}

int main() {
	int n,m;
	cin>>n;
	cin>>m;
	vector<vector<int>> graph(n);
	for(int i=0;i<m;i++)
	{
	    int x,y;
	    cin>>x;
	    cin>>y;
	    x--;
	    y--;
	    graph[x].push_back(y);
	    graph[y].push_back(x);
	}
	int result=0;
	vector<int> visited(n,-1);
	for(int i=0;i<n;i++)
	{
	    if(visited[i]==-1)
	    {
	        bfs(graph,visited,i);
	        int count=0;
	        for(int j=0;j<n;j++)
	        {
	            if(visited[j]==i)
	            {
	                count++;
	            }
	        }
	        result+=ceil(sqrt(count));
	    }
	}
	cout<<result<<endl;
	return 0;
}