11503 - Virtual Friends

[sabir]

i use union find algo and get tle.give any idea how to optimize time.

[jan_holmes]

I was using the same algorithm (union-find) in C++ and it was run under 1.6 secs. Anyway, in what language do you write your code ?

[sabir]

i also use c++.
here is my code

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define sz 1000010

long vertex[sz],rank[sz],len[sz];
long edge,top;

typedef struct
{
	char name[25];
}name_info;

name_info data[sz];

long Find_set(long num)
{
	if(num!=vertex[num])
	{
		vertex[num]=Find_set(vertex[num]);
	}

	return vertex[num];
}

long Link(long x,long y,long a,long b)
{
	long t1,t2;

	if(rank[x]>rank[y])
	{
		t1=len[x];
		t2=len[y];

		len[x]=len[y]=t1+t2;

		vertex[x]=vertex[y];
	}
	else
	{
		t1=len[x];
		t2=len[y];

		len[x]=len[y]=t2+t1;	

		vertex[y]=x;

		if(rank[x]==rank[y])
		{
			rank[y]++;
		}
	}

	return t1+t2;
}


long UNION(long x,long y)
{
	return Link(Find_set(x),Find_set(y),x,y);
}

int check(char str[])
{
	long i,y;

	for(i=1;i<=top;i++)
	{
		y=strcmp(data[i].name,str);
		if(y==0)
		{
			return i;
		}
	}

	top++;
	
	len[top]=1;
	rank[top]=0;
	vertex[top]=top;
	
	strcpy(data[top].name,str);

	return top;
}

int main()
{
	//freopen("11503in.txt","r", stdin);
	//freopen("11503out.txt","w", stdout);

	long i,t,ans,x,y;
	char name1[25],name2[25];

	scanf("%ld", &t);

	while(t--)
	{
		scanf("%ld", &edge);
		top=0;
		for(i=1;i<=edge;i++)
		{
			scanf(" %s %s", name1,name2);
			
			x=check(name1);
			y=check(name2);

			if(Find_set(x)!=Find_set(y))
			{
				ans=UNION(x,y);
			}

			printf("%ld\n",ans);
		}
	}

	return 0;
}

i use len[] to get total connected components of the parents every vertex.

[el cheeto]

Hi, I am also using Union-Find algorithm, but also getting TLE, any help would be great. Thank you.

My union-find algorithm is the following:

void make_set(int x)
{
p[x] = x;
rank[x] = 0;
}

void link(int x, int y)
{
if (rank[x] > rank[y])
p[y] = x;
else
{
p[x] = y;
if (rank[x] == rank[y])
rank[y] = rank[y] + 1;
}
}

int find_set(int x)
{
if (x != p[x])
p[x] = find_set(p[x]);
return p[x];
}

void union_set(int x, int y)
{
link(find_set(x), find_set(y));
}

[mmonish]

>>sabir
my algorithm is same as ur's. I think u should use efficient data structure for ur check() function. in worst case ur complexity is O(n^2) where n = 100000. For this i use stl map. Hope this helps u.....

[el cheeto]

ACC now!! I used map and got accepted. Thank you!!

[L I M O N]

i use union find algo and get tle.give any idea how to optimize time.

visit http://www.youngprogrammer.com compare your solution and fix bugs.

[azk84]

I'm getting TLE and I have no idea how to improve my running time! Plz help me . Here is my code:

Code: Select all

AC. . .

[azk84]

I found my silly mistake
I used union-find algo with stl map, and my running time is 5.
How can I improve this running time? In ranking list exist running times under 0.5 seconds

[StraightForward]

Hi... I Am New At Acm.. I Did Try Virtual Friends Using Map In Java.. But I Get WA here is my Code...

Thanks BeforeHand.... Christian Ortiz Venezuela...
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
static Hashtable<String,Integer> Map;
public static void main(String[] args) throws Exception
{
//BufferedReader In = new BufferedReader(new InputStreamReader(System.in));
BufferedReader In = new BufferedReader(new FileReader(new File("In.in")));
PrintWriter Out = new PrintWriter(System.out);
Integer MAX = new Integer(In.readLine().trim());
for(Integer I=1;I.compareTo(MAX)<=0;I++)
{
Integer Max = new Integer(In.readLine().trim());
Map = new Hashtable<String,Integer>();
Integer Count = new Integer(0);
for(Integer D=1;D.compareTo(Max)<=0;D++)
{
StringTokenizer x = new StringTokenizer(In.readLine());
String X = new String(x.nextToken());
String Y = new String(x.nextToken());
if (Map.containsKey(X) && !Map.containsKey(Y)) //One Friend... New..
{
++Count;
Map.put(new String(Y),0);
}
if (!Map.containsKey(X) && Map.containsKey(Y)) //Other Friend New...
{
++Count;
Map.put(new String(X),0);
}

if (!Map.containsKey(X) && !Map.containsKey(Y) && D.equals(1)) //Two New Friends...
{
Count+= 2;
Map.put(new String(X),0);
Map.put(new String(Y),0);
}
Out.println(Count);
}
}
Out.flush();
return;
}
}

[roticv]

Try

Code: Select all

1
5
A B
B C
D E
A D
A C

[wjomlex]

I'm getting RE, and I don't see why. My arrays are much larger than necessary, and I can't find any infinite loops or anything. Is the input formatting different from what the problem says? Can things be split across lines?

Code: Select all

//UVa Problem 11503 - Virtual Friends
//Wesley May - Jan 27 2009 (RE... Array indexes should be fine... maybe HashMap?)

import java.util.*;
import java.io.*;

public class Main
{
	static int[] p, s;

	public static void main(String args[]) throws IOException
	{
		
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		int t = Integer.parseInt(scan.readLine());

		for(int ca=0;ca < t;ca++)
		{
			int n = Integer.parseInt(scan.readLine());

			p = new int[1000000];
			s = new int[1000000]; //size of set with leader i

			for(int i=0;i < p.length;i++)
			{
				p[i] = i;
				s[i] = 1;
			}

			HashMap h = new HashMap();
			int count = 0;

			for(int i=0;i < n;i++)
			{
				StringTokenizer st = new StringTokenizer(scan.readLine());

				String a = st.nextToken();
				String b = st.nextToken();
				int ia,ib;

				Object o = h.get(a);
				if(o == null)
				{
					ia = count++;
					h.put(a,ia);
				}
				else
					ia = (Integer)o;

				o = h.get(b);
				if(o == null)
				{
					ib = count++;
					h.put(b,ib);
				}
				else
					ib = (Integer)o;

				if(find(ia) == find(ib))
					sb.append(s[find(ia)]).append("\n");
				else
				{
					s[find(ib)] = s[find(ia)] + s[find(ib)];
					union(ia, ib);
					sb.append(s[find(ia)]).append("\n");
				}
			}
		}

		System.out.print(sb);
	}

	public static int find(int i)
	{
		if(p[i] == p[p[i]])
			return p[i];

		p[i] = find(p[i]);
		return p[i];
	}

	public static void union(int i, int j)
	{
		int ri = find(i);
		int rj = find(j);

		p[ri] = rj;
	}
}

I'm having the same problem with Problem 11504...

[Obaida]

Hi every one i went for a funny method & don't know if it works or not.
This time seems not working cause i got WA. But is there any mistake in my algo?

Code: Select all

removed

[kbr_iut]

This problem is solvable with union-find algorithm.
I didnt see ur code.
but ur code fails to give correct answer for the input posted by "roticv "
input

Code: Select all

1

5
A B
B C
D E
A D
A C

output

Code: Select all

2
3
2
5
5

but ur code gives

Code: Select all

2
3
5
5
5

hope it will help out.

[vahid sanei]

I got Acc in 2.920 sec , how can i reduce time of my algo ?
I use union-find and map




thanks in adnance