10583 - Ubiquitous Religions

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 10583 - Ubiquitous Religions

Post by hamedv » Wed Jun 25, 2008 10:37 am

Hi

I'm getting WA but i don't know why does my code fail?
I have checked it with many I/O from this site: http://uvatoolkit.com/
Please give me an input that my code gives wrong answer to it?

Code: Select all

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define foreach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define dvar int
#define iterator(c) ( __typeof( (c).begin() ) )
#define all(c) c.begin(), c.end()
#define vecshoot(c) { int __i; foreach(__i, c) cerr << " " << (*__i) ; cerr << endl; }

vector<int> gl[50010];
int ig[50010];

int main()
{
	int l = 1, n, m;
	while (cin >> n >> m, n||m)
	{
		for (int i = 1; i <= n; i++)
		{
			ig[i] = i;
			gl[i].clear();
			gl[i].push_back(i);
		}
		for (int i = 0; i < m; i++)
		{
			int a, b;
			cin >> a >> b;
			int ag = ig[a];
			int bg = ig[b];
			if (ag == bg)
				continue;
			int bgs = gl[bg].size();
			for (int j = 0; j < bgs; j++)
				gl[ag].push_back(gl[bg][j]);
			for (int j = 0; j < gl[ag].size(); j++)
				ig[gl[ag][j]] = a;
			gl[bg].clear();
		}
		int c = 0;
		for (int i = 1; i <= n; i++)
			if (gl[i].size())
				c++;
		cout << "Case " << l++ << ": " << c << endl;
	}
  return 0;
}
Thanx

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

Re: 10583 - Ubiquitous Religions

Post by thomas1016 » Mon Dec 08, 2008 8:48 pm

input

Code: Select all

3 3
1 1
2 2
3 3
3 3
1 1
1 1
1 1
0 0

output

Code: Select all


Case 1: 3
Case 2: 3

dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 10583 - Ubiquitous Religions

Post by dhruba07 » Thu Dec 05, 2013 11:18 pm

I looped through the whole array from 1 to number of students and incremented the counter whenever I got a parent index equal to the main index(Union find algorithm).Is there any other approach to solve this problem without running a loop from 1 to number of students?
Accept who you are :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10583 - Ubiquitous Religions

Post by brianfry713 » Fri Dec 06, 2013 9:57 pm

To initialize union find you'll have to loop through all n students. Instead of looping through all n students to count the answer you could instead keep track of how many union operations were needed.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 105 (10500-10599)”