Algorithm
Problem link- https://www.spoj.com/problems/FOXLINGS/
FOXLINGS - Foxlings
It’s Christmas time in the forest, and both the Fox and the Wolf families are celebrating. The rather large Fox family consists of two parents as well as N (1≤N≤109) little Foxlings. The parents have decided to give their children a special treat this year – crackers! After all, it’s a well-known fact that Foxen love crackers.
With such a big family, the parents can’t afford that many crackers. As such, they wish to minimize how many they give out, but still insure that each Foxling gets at least a bit. The parents can only give out entire crackers, which can then be divided and passed around.
With this many children, not all of them know one another all that well. The Foxlings have names, of course, but their parents are computer scientists, so they have also conveniently numbered them from 1 to N. There are M (1≤M≤105) unique two-way friendships among the Foxlings, where relationship i is described by the distinct integers Ai and Bi (1≤Ai,Bi≤N), indicating that Foxling Ai is friends with Foxling Bi, and vice versa. When a Foxling is given a cracker, he can use his tail to precisely split it into as many pieces as he wants (the tails of Foxen have many fascinating uses). He can then pass these pieces around to his friends, who can repeat this process themselves.
Input
Line 1: 2 integers, N and M
Next M lines: 2 integers, Ai and Bi, for i=1..M
Output
A single integer – the minimum number crackers must be given out, such that each Foxling ends up with at least a small part of a cracker.
Example
Input: 9 5 3 1 6 1 7 6 2 7 8 9 Output: 4
Explanation of Sample:
The parents can give one cracker to Foxling 6, who will then split it into three and give pieces to his friends (Foxlings 1 and 7). Foxling 7 can then give half of his piece to his other friend, Foxling 2.
They can give another cracker to Foxling 8, who will split it with Foxling 9.
This leaves Foxlings 4 and 5, who have no friends (don’t worry, Foxen have long since outgrown the need for friends), and who must be given one cracker each. This brings the total up to 4 crackers.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 2e5+5;
int n, m;
int parent[MAXN];
int size[MAXN];
int cnt;
void init(){
for(int i = 1;i <= 2*m; i++){
parent[i] = i;
size[i] = 1;
}
}
int root(int i){
while(i != parent[i]){
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
bool find(int a, int b){
return root(a) == root(b);
}
void union1(int a, int b){
int root_a = root(a);
int root_b = root(b);
if(root_a == root_b)
return;
if(size[root_a] < size[root_b]){
parent[root_a] = root_b;
size[root_b] += size[root_a];
}else{
parent[root_b] = root_a;
size[root_a] += size[root_b];
}
}
int main(){
io;
unordered_map<int, int> M;
cin >> n >> m;
init();
cnt = 1;
for(int i = 0;i < m; i++){
int a, b;
cin >> a >> b;
if(M.find(a) == M.end()){
M[a] = cnt;
cnt++;
}
if(M.find(b) == M.end()){
M[b] = cnt;
cnt++;
}
int u = M[a];
int v = M[b];
union1(u, v);
}
unordered_set<int> S;
for(auto p : M){
// cout << p.first << " " << p.second << endl;
S.insert(root(p.second));
}
int ans = S.size() + (n - M.size());
cout << ans << endl;
return 0;
}Input
3 1
6 1
7 6
2 7
8 9
Output
Demonstration
SOPJ Solution-Foxlings-Solution in C, C++, Java, Python