10583 - Ubiquitous Religions

[hamedv]

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]

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]

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?

[brianfry713]

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.