ProbToreal: UVa - 13153 ( Number Of Connected Components ) [ Analysis + Solution ]

=>Try Yourself First. For help Scroll Down .

Problem Link: https://uva.onlinejudge.org/external/131/13153.pdf

⇒ Problem Clearance:

You will be given N numbers which is between 1 & 10⁶ . And you can draw an edge between any two number if the Greatest Common Divisor ( GCD ) of those two number is greater than 1 . Hence you made some conntection ( probably none ) among the nodes. Now you're going to find number of component that are connected together.

⇒ Required Knowledge:

Sieve of Erathothense + Prime Factorization + Depth First Search / Disjoint Set Union .

😤 Wow!!! Got the idea how to solve ??? Then Code it.😤

😡 Not Yet !! Continue Reading . 😡

⇒ How To Solve ??: 

1) Generate primes upto 10⁶ . 

2) Then for each of the A_ith number find out the Prime Factorization. And connect those prime with that number.
How to connect ??? 
Well, I solved the problem using the Disjoint Set Union algorithm. Suppose I got the primes P1, P2, P3, P4, .....  Now for each of them I put them into the same union with same Parent for each of the number. If you don't get the previous line then you must read about DSU first. 

That's how we connect the Primes with a specific number.
3) Almost 75% of the work has done. In this step, you just have to count how many different parent you got till now . You can do this by checking each parent of A_ith .
Voila !!! Solved !!! 











⇒ Wrong Answer ????

Just think a bit. Is there any implementation error you did? Try to give an input of N prime number and see whether the result is N or not ? I mean check the result of following case is 4 or Not ? 
4
2 3 5 7
Try several cases like this . If they are giving correct output then there may be some corner case you missed. Try to open the next spoiler hint for you.

⇒ Spoiler :

If you did not any implementation mistake in your code then your should be solved by now. If you're failed to solve yet then you may see the Solution given below or you may read the whole post once again and then code it again.

⇒ Code:

	/ Jai Shree Ram /
	/ ssavi. ICT-4 CoU /

	#include<bits/stdc++.h>
	#define DIST(x1,x2, y1, y2) sqrt(((x1-x2)(x1-x2))+((y1-y2)(y1-y2)))
	#define DIST3D(x1,x2, y1, y2, z1, z2) (((x1-x2)(x1-x2))+((y1-y2)(y1-y2)) + ((z1-z2)*(z1-z2)))
	#define CLR(a) a.clear()
	#define VCLR(a, n) for(int i=0; i<=n+3; i++) a[i].clear()
	#define SIZE(a) a.size()
	#define ERASE(a, b) memset(a, b, sizeof a)
	#define pb push_back
	#define LL long long
	#define ULL unsigned long long
	#define DBG cout<<"I Am Here"<<endl
	#define DBGA(a) cout<<a<<endl
	#define DBGI(b,a) cout<<b<<' '<<a<<endl
	#define DBGL(i,s,e,b) or(int i=s; i<=e; i++) cout<<b<<endl
	#define INF 1e9
	#define INV 1e-6
	#define SF(a) scanf("%I64d", &a)
	#define PF(a) printf("%I64d\n", a)
	#define sf(a) scanf("%d", &a)
	#define pf(a) printf("%d\n", a)
	#define pii pair<int,int>
	#define PIS pair<double,string>
	#define PII pair<LL,LL>
	#define MAX 600005
	#define CASE(i) printf("Case %d:", i);
	#define PI acos(-1)
	#define piis pair<int, string>
	#define fast1 ios_base::sync_with_stdio(false);
	#define fast2 cin.tie(0)
	#define CHECK_BIT(var,pos) ((var & (1 << pos)) == (1 << pos))
	#define LOOP(i, b, n) for(int i=b; i<=n; i++)
	#define nl puts("")
	#define popcount __builtin_popcount
	#define valid(i,j,m,n) (i>=0 && i<n && j>=0 && j<m)
	#define all(v) v.begin(), v.end()

	using namespace std;

	const int MAXN = 1000005;
	int status[(MAXN/32)+10];
	int primelist[MAXN], primesz;

	bool check(int n, int pos) { return (bool)(n & (1<<pos)); }
	int SET(int n, int pos){ return n=n\|(1<<pos);}

	void sieve()
	{
	int sqrtN=int (sqrt(MAXN));
	//for(int j=4; j<MAX; j=j+2)
	//status[j>>5]=SET(status[j>>5],j&31);
	for(int i=3; i<=sqrtN; i=i+2)
	{
	if(check(status[i>>5],i&31)==0)
	{
	for(int j=i*i; j<=MAXN; j= j + (i<<1))
	{
	status[j>>5]=SET(status[j>>5],j&31);
	}
	}
	}

	primelist[primesz++] = 2;
	for(int i=3; i<=MAXN; i=i+2)
	{
	if(check(status[i>>5],i&31)==0){
	primelist[primesz++] = i;
	// cout<<i<<endl;
	}
	}
	}

	bool present[1000003];
	int ARR[100003];
	int parent[1000003];

	int findParent(int i,int parent[])
	{
	if(parent[parent[i]]!=parent[i])
	parent[i]=findParent(parent[i],parent);
	return parent[i];
	}
	void unionNodes(int a,int b,int parent[])
	{
	int parent_a=findParent(a,parent),parent_b=findParent(b,parent);
	if(parent_a==parent_b)
	return;
	parent[parent_a]=parent_b;
	return;
	}

	void FACTO(int Num)
	{
	int TMP = Num;
	for(int i=0; i<primesz && primelist[i]<=sqrt(Num); i++){
	if(TMP%primelist[i]==0){
	while(TMP%primelist[i]==0){
	TMP = TMP/primelist[i];
	}
	unionNodes(primelist[i], Num, parent);
	}
	}
	//cout<<TMP<<endl;
	if(TMP>1){
	unionNodes(TMP, Num, parent);
	}
	}

	void init()
	{
	for(int i=0; i<1000003; i++){
	present[i] = false;
	parent[i] = i;
	}
	}

	int main()
	{
	//freopen("file.txt", "r", stdin);
	//freopen("fileOut.txt", "w", stdout);
	sieve();
	int test;
	scanf("%d", &test);
	LOOP(caseno, 1, test)
	{
	init();
	int n, maxval = 0, cnt = 0;
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
	int X;
	scanf("%d", &X);
	ARR[i] = X;
	maxval = max(maxval, X);
	if(X>1){
	FACTO(X);
	}
	else{
	cnt++;
	}
	}

	for(int i=1; i<=n; i++){
	if(ARR[i]>1){
	int baba = findParent(ARR[i], parent);
	if(!present[baba]) cnt++;
	present[baba] = true;
	}
	}
	CASE(caseno);
	printf(" %d\n", cnt);
	}
	}

view raw UVa - 13153 ( Number of Connected Components ).cpp hosted with ❤ by GitHub

=>Leave a comment for any kinds of Hugs and / or Bugs. Thank you .

ProbToreal

Search Here

Navigation

Tuesday, April 25, 2017

UVa - 13153 ( Number Of Connected Components ) [ Analysis + Solution ]

Problem Link: https://uva.onlinejudge.org/external/131/13153.pdf

2 comments: