10608 - Friends

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

Moderator: Board moderators

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

Re: 10608 Why RE??

Post by brianfry713 » Fri Apr 20, 2012 8:56 pm

Input:

Code: Select all

2
2 1
1 2
2 1
1 2
AC output:

Code: Select all

2
2
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

Re: 10608 Why RE??

Post by cse.mehedi » Tue May 15, 2012 9:28 pm

brianfry713 wrote:Input:

Code: Select all

2
2 1
1 2
2 1
1 2
AC output:

Code: Select all

2
2
TLE!!!!!!!!!

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

Re: 10608 Why RE??

Post by brianfry713 » Tue May 15, 2012 10:52 pm

Input:

Code: Select all

2
2 1
1 2
3 1
2 3
AC Output:

Code: Select all

2
2
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

Re: 10608 Why RE??

Post by cse.mehedi » Fri May 25, 2012 2:08 pm

I modified my code but i am getting RE :oops: :oops: :oops:

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

Re: 10608 Why RE??

Post by brianfry713 » Fri Jun 01, 2012 1:54 am

This won't compile on my system.
You have these globals defined:
bool adj_mat[size][size],visited[size];
This isn't a declaration:
adj_mat[size][size]={0},visited[size]={0];
You can't access beyond adj_mat[size-1][size-1].
To clear an array using ={0} you must do it at declaration. You could try using memset() instead.
Check input and AC output for thousands of problems on uDebug!

ojha
New poster
Posts: 7
Joined: Wed May 22, 2013 9:07 am

Re: 10608 - Friends

Post by ojha » Sun Jul 28, 2013 9:44 am

Why the hell am I getting WA ??

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int>par;

int find(int r){
    if(par[r] == r)
        return r;
    else
        return par[r] = find(par[r]);
}

void Union(int a, int b){
    int u = find(a);
    int v = find(b);

    if(u != v)
        par[v] = u;

    return;
}

int main(){

    int time, n, m, i, a, b, max;
    cin >> time;

    while(time--){
        cin >> n >> m;

        max = 0;

        vector<int>count(n + 1, 0);
        for(i = 0; i<=n; i++){
            par.push_back(i);
            //count.push_back(0);
        }

        for(i = 0; i<m; i++){
            cin >> a >> b;

            Union(a, b);
        }

        for(i = 1; i<=n; i++){
            count[par[i]]++;
            if(count[par[i]] > max)
                max = count[par[i]];
        }

        cout << max << endl;
        par.clear();
    }
    return 0;
}

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

Re: 10608 - Friends

Post by brianfry713 » Mon Jul 29, 2013 5:15 am

Change line 49 to:
count[find(i)]++;
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10608 - Friends

Post by uDebug » Fri Jan 31, 2014 2:00 pm

I found these test cases useful while testing / debugging.

Please note that some test cases I culled and then modified from earlier posts in this thread and the credit goes to the OPs.

Code: Select all

6
10 12
1 2
3 1
3 4
5 4
3 5
4 6
5 2
2 1
7 10
1 2
9 10
8 9
3 5
1 2
2 3
1 1
2 2
3 3
10 9
1 2
2 3
3 3
1 1
2 1
4 5
5 7
3 4
7 5
200 16
1 2
2 3
3 4
5 66
66 7
7 8
4 66
99 10
24 25
62 65
66 66
24 99
10 62
11 12
10 11
200 199
1 1
1 1
100 9
99 10
24 25
62 65
66 66
24 99
10 62
11 12
10 11
100 62
AC Input:

Code: Select all

6
3
6
8
1
9
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Ahmad93
New poster
Posts: 6
Joined: Wed Mar 05, 2014 6:39 pm

Re: 10608 - Friends

Post by Ahmad93 » Wed Mar 05, 2014 6:50 pm

My code shows correct output but still getting wrong answer. :oops: Please help.

Code: Select all

#include<stdio.h>
int group[500001],a[30001];
void main()
{
	int i, j, k, l, n, m, test,maxNum,max,len;
	scanf("%d", &test);
	while (test--)
	{
		scanf("%d %d", &n, &m);
		
		for (i = 1; i <= n; i++)a[i] = 0;
		
		len = 1, maxNum = 0;
		for (i = 0; i < m; i++)
		{
			scanf("%d %d", &k, &l);
			if (maxNum < k)maxNum = k;
			if (maxNum < l)maxNum = l;
			
			if (!a[k] && !a[l])
			{
				group[len] = 2;
				if (k == l)group[len]--;
				a[k] = a[l] = len;
				len++;
			}

			else if (a[k] && !a[l])
			{
				group[a[k]]++;
				a[l] = a[k];
			}
			
			else if (!a[k] && a[l])
			{
				group[a[l]]++;
				a[k] = a[l];
			}
			
			else if (a[k] && a[l])
			{
				if (a[k] != a[l])
				{
					group[a[k]] += group[a[l]];
					group[a[l]] = 0;
					for (j = 1; j <= maxNum; j++)
					{
						if (a[j] && a[j] == a[l])
							a[j] = a[k];
					}
				}
			}

		}
		max=0;
		for (j = 1;j<len; j++)
			if (max < group[j])max = group[j];
		printf("%d\n", max);
	}
}

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

Re: 10608 - Friends

Post by brianfry713 » Wed Mar 05, 2014 10:55 pm

if M == 0 print 1.
Check input and AC output for thousands of problems on uDebug!

Ahmad93
New poster
Posts: 6
Joined: Wed Mar 05, 2014 6:39 pm

Re: 10608 - Friends

Post by Ahmad93 » Sun Apr 06, 2014 4:05 pm

brianfry713 wrote:if M == 0 print 1.
Thank you brianfry713. That was a great mistake. I have corrected my code. But still getting wrong answer. I failed to figure out the mistake.

Code: Select all

#include<stdio.h>

int member[15001],a[30001];
void main()
{
	int i, j, A, B, N, M, test,maxNum,max,group;
	scanf("%d", &test);
	while (test--)
	{
		scanf("%d %d", &N, &M);
		
		for (i = 1; i <= N; i++)a[i] = 0;
		
		group = 1, maxNum = 0;
		for (i = 0; i < M; i++)
		{
			scanf("%d %d", &A, &B);
			
			if (maxNum < A)maxNum = A;
			if (maxNum < B)maxNum = B;
			
			if (!a[A] && !a[B])
			{
				member[group] = 2;
				a[A] = a[B] = group;
				group++;
			}

			else if (a[A] && !a[B])
			{
				member[a[A]]++;
				a[B] = a[A];
			}
			
			else if (!a[A] && a[B])
			{
				member[a[B]]++;
				a[A] = a[B];
			}
			
			else if (a[A] && a[B])
			{
				if (a[A] != a[B])
				{
					if (member[a[A]] > member[a[B]])
					{
						member[a[A]] += member[a[B]];
						member[a[B]] = 0;
						for (j = 1; j <= maxNum; j++)
						{
							if (a[j] && a[j] == a[B])
								a[j] = a[A];
						}
					}

					else
					{
						member[a[B]] += member[a[A]];
						member[a[A]] = 0;
						for (j = 1; j <= maxNum; j++)
						{
							if (a[j] && a[j] == a[A])
								a[j] = a[B];
						}
					}
				}
			}

		}
		max=1;
		for (i = 1;i<group; i++)
			if (max < member[i])max = member[i];
		printf("%d\n", max);
	}
}

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

Re: 10608 - Friends

Post by brianfry713 » Mon Apr 07, 2014 9:47 pm

Input:

Code: Select all

100
26 8
4 19
23 11
26 4
19 21
25 26
6 5
16 8
17 7
10 7
4 10
6 4
6 10
7 5
5 1
3 6
7 3
4 9
3 2
2 3
1 3
1 4
4 3
4 1
3 2
4 3
2 4
27 23
22 18
3 7
8 15
3 18
22 23
13 11
23 16
3 22
17 1
9 16
5 6
2 21
27 15
16 4
14 10
10 17
5 6
20 8
23 15
3 9
25 19
25 21
7 27
13 36
1 13
11 13
1 2
7 8
6 13
7 12
8 6
4 11
11 1
8 13
1 8
5 3
13 2
1 5
6 5
12 6
6 11
2 1
3 7
2 9
5 9
3 11
8 13
11 2
1 13
11 5
2 10
7 3
9 2
6 1
12 2
9 2
2 11
8 5
6 2
13 10
11 32
11 4
10 7
11 6
7 11
8 11
10 5
4 6
4 8
9 3
6 10
10 8
3 7
8 2
5 4
4 9
1 10
7 9
4 2
7 10
1 5
3 2
9 4
10 4
6 4
1 2
9 8
4 2
11 5
5 9
8 9
5 9
7 9
3 22
1 2
2 1
3 2
1 3
3 2
2 1
3 1
2 3
1 2
1 3
1 3
3 2
1 2
2 1
3 2
3 2
1 3
2 1
1 2
1 2
1 2
3 1
16 31
16 4
14 1
12 9
1 2
6 7
16 4
9 15
1 12
8 13
9 12
9 12
7 15
3 13
2 5
13 1
9 10
1 4
5 7
8 5
11 1
3 11
12 11
7 4
6 15
15 12
13 2
9 2
7 10
7 3
11 15
12 11
18 8
12 11
1 16
13 15
8 11
17 15
7 11
11 5
4 17
30 41
23 14
28 29
26 2
19 15
14 28
23 6
2 28
25 20
6 12
23 15
20 23
5 16
3 28
26 4
18 15
24 13
16 12
20 22
10 4
27 3
1 13
23 29
24 15
29 17
21 2
6 3
6 18
6 1
13 23
16 7
6 23
10 17
14 11
20 2
14 21
14 28
19 29
4 1
12 2
9 2
3 15
26 27
14 5
3 12
2 18
20 19
10 16
9 4
22 26
17 5
26 25
5 15
12 20
23 21
13 17
21 6
1 10
13 3
23 14
22 17
6 5
6 16
10 3
15 3
8 15
1 13
22 5
4 10
1 26
20 44
20 6
17 10
15 1
12 13
12 9
17 5
8 20
6 11
11 16
1 16
4 5
2 4
20 3
13 8
2 12
17 10
2 15
15 13
15 4
17 14
15 14
10 17
20 5
8 1
4 20
20 18
11 1
11 13
1 12
7 8
17 14
3 5
19 17
19 3
2 8
12 13
4 5
14 12
17 10
11 16
7 14
8 17
4 18
9 5
2 17
1 2
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
9 45
8 6
9 5
3 8
7 3
7 9
8 6
1 3
7 1
7 4
8 4
4 3
7 2
8 6
2 8
4 8
4 9
2 3
5 4
8 9
7 3
6 3
8 6
5 4
6 9
5 2
3 8
2 9
7 9
3 7
6 5
5 7
4 5
7 6
8 3
5 3
6 2
6 2
7 8
3 2
8 7
1 8
4 3
6 1
9 6
7 3
22 45
12 18
14 11
13 17
13 4
20 8
13 6
17 21
14 9
6 4
16 3
11 22
7 14
19 3
5 21
12 15
22 1
8 13
12 20
6 22
1 3
7 11
6 1
10 19
7 13
1 21
15 9
18 19
20 14
20 22
11 9
14 10
9 21
21 18
19 4
4 21
6 9
20 13
3 4
3 1
22 16
9 18
12 4
4 17
5 2
16 3
11 45
4 1
4 7
10 7
2 5
8 2
3 6
2 9
1 11
2 8
9 5
2 1
8 4
2 10
4 8
8 7
6 10
3 1
7 11
3 2
6 5
11 8
6 10
4 1
3 5
11 9
9 10
7 1
6 2
6 11
9 7
2 11
8 6
8 10
7 2
1 2
6 9
7 10
8 10
10 8
2 9
5 8
6 10
8 11
9 8
7 8
3 46
3 2
2 3
1 2
1 2
1 3
3 2
3 2
2 1
3 1
2 1
2 1
1 3
1 3
3 2
1 2
1 3
2 1
3 2
1 2
2 3
3 2
3 2
2 1
1 3
1 3
2 1
3 2
2 3
2 3
1 3
1 2
3 1
2 1
2 3
3 2
1 2
3 2
1 3
1 2
3 2
2 3
3 1
3 1
2 1
1 2
1 2
30 25
10 25
16 30
21 2
19 22
26 15
19 25
7 24
19 7
14 28
10 1
25 18
8 23
17 24
6 11
12 5
17 21
21 24
20 4
25 1
25 12
15 6
6 13
29 16
19 12
13 28
4 19
4 2
2 4
4 2
4 2
3 4
4 2
3 4
2 4
3 1
4 1
1 4
4 1
3 2
4 2
4 3
3 4
3 1
3 4
3 1
27 32
9 2
25 9
23 22
12 20
9 27
11 27
17 26
13 11
9 8
16 1
7 8
9 19
7 25
18 19
13 5
13 22
22 27
3 6
21 14
25 2
2 24
17 18
12 2
1 20
9 6
9 16
13 18
23 19
4 13
27 17
6 12
11 16
20 48
14 12
2 17
11 19
11 16
12 19
14 9
12 5
12 10
11 16
11 13
15 3
5 2
15 1
15 7
4 7
7 9
18 20
6 1
11 8
8 2
18 13
10 9
17 2
18 19
9 20
4 15
3 20
16 9
20 3
8 15
1 14
16 18
6 13
10 16
20 17
17 9
2 18
17 18
11 7
9 20
6 12
14 20
11 2
1 2
16 8
17 16
13 4
5 18
6 4
3 5
3 5
3 4
4 1
1 0
18 28
3 18
14 3
11 10
12 8
9 18
17 16
3 11
15 8
1 16
10 14
11 10
15 6
5 3
13 2
15 13
17 9
15 9
16 9
16 5
6 12
2 9
5 14
14 3
11 6
14 17
9 7
6 5
6 3
16 47
9 16
16 10
13 10
2 14
16 5
12 11
11 2
12 11
6 1
14 8
13 6
6 10
7 1
2 8
15 7
7 8
6 7
1 2
16 2
16 15
6 11
9 1
12 4
11 1
4 8
8 16
10 3
14 11
10 12
3 6
7 3
8 6
4 7
4 10
1 12
10 12
15 4
12 3
11 4
2 7
16 11
10 13
5 3
9 5
3 11
11 9
14 2
4 8
4 1
2 4
4 3
1 4
1 2
3 1
1 4
2 1
4 22
1 3
1 4
1 3
2 1
2 3
2 4
3 2
3 1
1 3
3 1
1 4
4 2
4 1
4 1
3 1
4 1
4 3
1 2
4 3
4 2
3 2
4 2
9 38
4 2
6 9
2 5
2 3
1 8
5 8
3 1
2 4
6 7
4 8
2 5
5 8
2 4
2 4
3 7
1 4
6 2
9 1
3 8
1 3
4 6
1 4
4 9
7 8
6 9
4 5
2 8
3 1
2 4
9 5
4 2
3 7
7 4
9 2
7 1
3 1
7 1
6 4
19 0
8 45
2 7
8 4
5 8
3 8
3 4
1 8
5 8
3 6
8 6
7 4
7 1
3 7
8 1
5 2
8 7
4 7
3 8
6 5
7 1
8 2
3 1
1 7
8 3
4 7
8 3
3 7
3 5
5 3
5 1
3 1
6 8
5 4
8 5
5 2
8 4
7 4
3 7
6 5
5 8
2 5
1 5
1 7
2 4
4 2
3 4
23 10
10 23
9 11
21 2
13 17
10 6
5 17
14 21
11 18
19 12
22 3
28 21
26 13
11 26
15 28
3 24
25 24
26 10
20 8
27 5
11 17
5 22
6 4
20 2
6 22
15 4
18 25
13 18
9 5
10 24
17 25
3 25
20 13
15 20
12 4
7 3
12 3
4 2
14 2
11 5
15 8
3 12
1 11
3 1
2 9
3 1
9 14
13 15
7 1
10 9
11 2
3 14
4 7
15 9
30 16
28 29
10 7
24 11
9 11
5 27
26 5
17 15
11 30
15 27
16 2
28 18
15 23
1 7
1 30
23 20
20 24
18 40
7 12
12 10
8 2
4 13
10 6
9 2
12 11
10 15
16 18
10 7
6 15
18 9
2 14
2 13
1 11
2 8
12 5
18 3
10 8
2 1
16 10
9 7
4 16
13 10
18 12
1 5
17 1
15 18
6 9
2 5
9 10
10 9
10 7
18 3
17 6
9 2
11 13
12 8
4 15
11 4
19 46
11 10
19 14
13 9
4 9
17 19
18 2
12 2
2 6
18 3
8 12
6 4
6 19
14 5
2 10
1 15
9 8
6 5
2 15
13 5
1 11
4 18
12 15
19 13
17 14
12 6
7 17
16 3
14 15
10 11
10 18
16 12
19 17
8 12
3 8
19 3
4 11
15 19
1 12
14 12
14 17
6 3
6 3
3 16
17 9
5 4
4 1
22 27
18 6
12 4
21 14
18 5
2 16
4 12
13 16
6 1
15 14
13 16
18 9
7 14
11 22
1 8
14 6
19 7
9 8
20 4
10 21
19 13
10 7
4 14
5 18
3 16
10 20
22 16
15 9
20 19
11 19
6 13
11 8
20 8
5 8
18 1
4 20
20 4
13 4
17 7
13 20
20 15
19 8
15 11
10 14
10 20
12 16
5 14
15 4
13 9
11 8
13 4
9 13
1 10
9 2
13 9
7 8
6 8
13 9
23 2
12 10
13 10
9 18
1 5
2 4
8 3
9 8
4 2
5 9
3 1
7 5
9 5
7 1
3 8
5 2
2 9
5 3
8 6
4 6
1 5
9 7
14 39
13 2
6 1
12 6
14 3
11 14
3 2
10 14
5 4
4 7
14 11
5 9
10 14
3 10
14 1
9 3
2 14
3 5
14 12
10 14
1 5
13 3
4 7
14 8
10 3
14 9
11 2
2 7
1 4
2 8
1 4
5 3
6 5
2 13
1 12
1 4
4 12
9 14
14 8
6 8
29 48
13 4
24 8
6 23
16 13
5 29
26 25
11 1
12 27
7 16
17 18
16 13
25 23
20 15
26 29
14 3
23 27
6 17
26 3
10 13
16 6
4 12
22 14
12 5
3 18
20 19
23 22
12 5
7 1
5 12
3 27
1 8
6 27
10 8
10 17
28 6
18 2
10 20
11 21
9 8
18 24
29 22
28 27
22 24
2 24
21 2
23 19
28 24
26 29
1 0
2 30
1 2
1 2
2 1
2 1
2 1
1 2
2 1
2 1
2 1
2 1
1 2
2 1
2 1
1 2
1 2
1 2
2 1
2 1
2 1
1 2
2 1
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
18 31
1 11
14 1
8 6
3 1
9 13
5 12
8 9
15 3
2 9
4 15
10 2
11 17
13 16
11 12
2 4
9 12
8 15
5 1
11 14
15 7
15 14
13 16
10 4
17 2
18 11
15 10
3 5
3 2
9 10
9 15
1 16
18 48
15 18
11 7
11 5
11 7
18 5
4 8
6 18
9 6
11 4
15 11
8 15
12 14
6 3
9 7
18 2
9 14
17 18
18 9
4 10
14 2
12 15
9 18
3 5
16 15
15 4
12 6
17 15
6 7
1 4
6 8
15 4
7 15
11 8
4 6
9 14
18 15
11 12
12 13
16 9
9 10
12 18
14 9
13 1
13 11
2 1
18 17
4 6
13 12
24 17
15 8
5 7
14 20
23 16
20 2
13 12
11 12
2 9
19 20
14 8
2 1
4 16
23 10
13 14
22 4
21 22
4 17
23 24
8 17
16 17
22 4
2 18
15 12
14 5
17 2
1 2
1 6
13 19
21 13
9 20
17 8
5 18
2 20
12 9
8 5
7 10
22 16
21 6
8 14
9 2
13 15
20 11
2 39
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1
2 1
2 1
2 1
1 2
2 1
2 1
2 1
2 1
2 1
2 1
2 1
1 2
2 1
1 2
1 2
1 0
30 48
25 18
18 9
24 5
28 17
20 10
3 13
20 1
13 25
7 16
10 15
9 27
10 20
28 10
15 20
12 15
20 6
24 8
6 9
4 25
26 23
4 20
27 24
20 2
10 18
17 19
2 17
7 12
7 26
15 16
19 26
13 12
3 18
21 7
12 8
21 8
27 10
1 16
11 10
4 19
20 27
6 18
30 4
13 5
16 19
20 5
14 3
16 9
12 28
15 43
5 12
13 8
9 8
9 4
4 5
7 1
11 4
14 7
8 12
9 1
5 6
5 11
6 10
15 13
2 12
12 10
12 5
5 15
1 12
15 7
10 3
2 12
13 15
3 6
11 4
13 8
1 2
10 13
3 9
10 5
6 13
6 2
2 3
1 9
14 7
9 8
11 6
7 5
3 9
8 7
8 15
1 3
12 3
26 10
16 4
17 10
8 5
9 10
15 20
13 15
9 16
6 15
19 2
7 10
22 15
9 21
8 5
2 22
1 12
3 8
9 3
14 6
22 17
9 5
2 17
11 5
12 18
9 18
6 21
19 7
5 5
2 4
5 2
4 1
3 5
2 3
16 10
14 3
9 6
9 16
6 10
4 1
13 15
5 10
13 7
14 11
14 4
29 22
28 7
26 14
5 28
7 19
8 15
10 18
18 6
20 15
14 8
4 20
6 1
8 21
26 5
15 16
13 7
18 11
6 14
17 2
13 23
13 12
8 22
22 17
10 1
8 1
25 36
18 4
22 20
10 25
4 20
2 10
6 4
13 3
10 12
1 20
13 12
21 20
24 1
23 6
4 15
21 8
3 15
13 24
9 22
24 15
17 2
1 22
7 13
1 19
2 1
13 14
15 10
10 13
12 8
20 17
24 15
6 16
25 17
13 25
2 8
4 8
20 6
1 0
28 40
1 9
19 24
6 28
3 13
23 5
2 12
11 12
11 14
10 21
2 3
25 19
8 2
24 27
14 7
18 13
13 2
22 3
26 27
2 12
11 9
28 12
4 10
8 26
8 1
18 21
16 26
11 23
27 18
5 12
24 23
9 8
24 14
23 5
12 8
1 6
16 28
2 20
22 21
17 1
5 19
15 33
6 15
11 7
4 8
15 9
11 10
2 11
1 4
14 7
12 3
12 4
3 11
2 5
15 8
4 12
7 14
10 2
13 15
6 14
15 6
7 3
5 7
11 3
14 7
12 2
2 6
12 3
11 3
10 6
7 8
4 1
9 1
15 7
6 7
27 23
9 18
13 14
1 18
20 15
21 14
10 8
5 25
25 3
9 17
21 3
1 9
2 1
25 5
25 10
20 3
13 17
21 14
4 10
4 12
24 13
25 6
20 18
19 6
6 30
5 2
1 2
1 3
5 3
1 3
3 5
1 3
6 5
2 6
3 6
3 4
3 4
2 6
4 6
3 5
5 1
1 5
4 3
1 2
3 4
6 2
3 2
2 6
1 5
3 2
2 6
6 3
5 4
1 6
1 6
24 13
20 1
17 5
22 20
18 23
16 11
2 17
12 20
7 21
21 20
12 7
15 5
14 13
13 8
16 36
3 6
16 15
6 8
3 4
1 10
15 10
5 16
6 1
12 2
8 10
6 13
6 10
4 14
16 7
3 15
5 8
6 15
2 9
2 3
2 16
12 4
2 1
3 7
1 14
7 14
4 13
7 8
10 7
14 12
5 2
3 11
16 4
3 1
6 4
1 2
7 2
26 39
18 6
1 10
4 22
21 3
24 1
18 9
16 4
12 10
10 7
13 20
26 7
3 22
18 14
21 11
19 12
18 19
23 21
16 17
26 15
20 17
23 14
12 14
17 25
25 2
6 12
23 5
20 26
26 11
15 22
21 7
9 14
1 6
9 19
24 8
7 17
24 6
7 11
19 23
10 18
9 8
6 4
5 3
9 4
7 5
3 6
2 5
1 3
5 9
17 45
11 16
12 6
4 1
7 10
10 2
9 6
4 11
7 3
7 10
3 6
3 4
8 1
15 3
14 3
13 14
12 17
10 7
16 17
1 7
5 13
8 12
6 14
12 9
10 5
12 17
5 17
10 1
11 5
5 7
10 8
6 2
9 3
13 1
13 7
11 9
11 13
17 3
17 3
10 13
13 3
15 9
10 7
7 6
8 3
2 8
12 11
7 10
2 5
7 8
5 3
11 3
12 11
5 9
1 9
10 11
1 12
9 1
3 22
1 2
1 2
2 1
1 3
3 2
3 2
1 3
2 1
2 3
3 2
2 3
3 2
2 1
2 1
2 3
1 2
3 1
2 3
1 3
2 1
2 1
2 1
11 32
2 4
8 9
10 6
2 1
8 4
10 2
4 9
10 1
7 8
7 1
8 3
8 11
9 10
11 1
10 7
8 11
10 2
8 5
8 3
5 9
9 3
9 4
9 4
2 3
4 9
3 1
7 11
10 3
6 5
11 4
6 3
8 2
27 34
10 24
1 6
24 11
27 21
17 27
12 23
15 25
22 2
3 10
18 14
2 13
11 4
10 19
11 7
7 2
11 6
25 12
11 10
11 10
3 17
9 3
12 13
17 23
14 19
5 4
21 23
6 21
26 15
12 26
10 7
16 20
12 14
20 23
23 20
23 33
6 18
1 8
4 3
17 4
15 3
23 13
15 6
4 19
6 19
12 5
21 5
14 15
19 18
16 3
1 19
1 23
7 19
7 10
21 18
8 7
20 7
19 5
6 16
17 11
11 23
15 8
21 5
22 10
16 8
12 10
4 7
9 10
2 16
15 16
1 12
5 1
8 12
2 7
10 6
3 5
1 2
1 7
15 6
3 13
6 11
13 14
7 1
6 13
2 13
9 7
13 25
8 10
2 1
9 10
12 1
7 2
10 4
10 5
5 7
8 11
7 12
9 5
10 1
1 2
12 9
13 2
11 9
1 9
9 7
13 7
12 11
13 5
6 7
5 1
5 2
1 3
25 19
2 18
11 1
3 11
10 9
6 12
11 4
25 8
19 6
10 7
20 19
15 20
5 11
4 20
16 23
17 19
17 2
19 22
14 3
5 22
22 39
8 21
8 5
12 10
15 18
20 1
9 21
1 21
14 13
16 14
21 15
2 13
1 16
16 19
13 10
20 8
6 3
6 11
8 18
21 20
11 16
20 18
15 18
14 6
9 7
17 5
22 18
17 22
9 8
16 19
16 11
5 21
14 8
9 19
1 5
16 12
19 13
5 11
8 18
14 16
28 11
9 13
9 15
5 13
17 4
15 4
21 17
15 28
6 23
11 3
4 1
9 26
25 31
10 22
2 20
8 25
17 23
6 7
24 20
10 1
1 10
12 19
21 2
1 3
19 24
11 25
6 17
17 2
23 4
23 24
23 7
25 14
4 6
23 2
2 7
4 5
18 15
25 13
18 25
17 12
23 2
13 5
20 6
6 17
11 4
9 11
9 8
9 8
10 9
14 49
7 2
11 2
6 12
6 8
14 10
12 13
13 5
8 5
8 3
4 9
4 8
3 7
5 8
12 10
8 6
9 14
6 1
6 11
6 5
7 2
4 9
5 9
9 8
4 13
14 4
3 2
10 13
11 3
4 5
4 2
11 9
13 1
12 3
5 3
6 9
12 1
1 13
11 14
2 13
1 11
11 10
11 13
14 7
11 4
9 5
10 5
5 7
7 2
5 11
15 47
8 15
12 1
14 2
15 3
1 10
14 8
14 2
12 14
10 12
14 12
3 4
7 4
1 6
11 7
6 13
2 13
13 5
14 3
13 5
5 13
14 10
6 5
12 9
3 6
5 1
9 14
5 8
9 12
13 4
3 10
1 11
8 5
15 13
8 12
9 12
10 7
11 10
7 6
15 11
6 1
1 2
8 9
13 12
12 15
7 4
10 6
9 1
25 17
23 18
1 24
21 2
17 4
3 18
24 10
5 9
1 9
5 3
10 13
25 3
11 9
23 11
25 12
5 24
24 2
9 17
15 36
6 8
11 2
13 5
6 13
5 2
3 9
9 7
12 4
12 11
7 3
5 1
13 15
13 6
11 12
9 2
13 6
9 15
11 4
11 15
5 13
8 13
9 8
2 3
7 15
2 5
8 6
13 12
11 14
11 3
5 6
6 7
5 3
12 4
15 7
7 15
6 5
21 27
4 17
1 18
13 18
17 5
9 3
1 11
4 2
8 3
20 17
16 4
13 21
19 17
8 10
19 17
3 4
18 6
20 16
1 11
11 17
13 19
19 13
6 20
12 11
20 8
7 15
11 17
14 8
27 33
22 4
27 15
4 24
19 27
23 7
23 13
26 17
25 10
6 8
12 6
4 5
4 10
26 23
10 7
19 12
5 13
15 20
17 7
16 8
6 27
3 1
12 17
6 26
26 27
6 27
5 25
4 8
24 2
19 6
8 11
17 1
12 21
20 17
6 36
1 6
6 3
4 6
2 1
4 3
2 6
5 3
6 2
4 1
4 2
6 1
5 2
6 4
6 1
1 6
1 5
5 3
6 4
5 6
2 4
2 5
5 6
1 3
1 3
4 1
5 2
6 5
6 5
1 5
6 5
4 2
1 5
3 2
1 2
5 3
5 3
15 12
6 7
13 15
13 5
7 10
13 7
6 9
15 6
7 2
13 2
15 8
4 6
3 4
28 44
23 9
13 6
21 23
14 13
1 15
8 18
21 1
11 13
26 16
24 27
8 20
22 26
28 14
2 18
21 24
10 17
13 14
24 28
17 9
12 1
7 19
18 27
3 12
23 28
27 18
10 6
9 15
15 21
28 16
10 4
24 3
5 8
16 28
7 16
8 18
1 27
20 18
25 22
14 4
5 12
21 26
2 14
12 28
6 24
28 18
27 11
13 15
2 28
14 9
28 6
10 28
4 2
1 12
7 14
15 12
10 20
21 23
28 9
20 10
3 4
25 5
15 22
25 26
21 37
4 14
7 10
10 5
14 3
16 9
1 20
15 17
3 9
17 21
15 20
1 9
7 16
4 13
2 21
17 6
5 19
17 10
14 18
8 6
4 6
4 18
21 5
3 14
2 18
11 2
3 17
15 6
8 17
5 2
20 7
20 15
14 3
20 4
18 4
9 21
7 11
16 6
1 0
18 3
12 4
5 11
3 10
8 6
8 1
2 1
8 1
5 8
7 8
4 6
30 19
29 19
12 14
11 12
20 28
18 30
7 10
28 1
7 6
9 19
22 6
5 21
20 9
7 22
14 20
18 5
1 16
24 13
21 4
16 2
1 0
1 0
12 10
5 11
11 7
12 1
8 12
4 3
11 9
8 11
4 5
3 4
2 5
AC output:

Code: Select all

5
7
4
12
13
11
3
16
5
28
21
20
2
9
22
11
3
13
4
23
20
4
1
17
16
4
4
9
1
8
3
12
14
14
18
19
21
11
4
3
9
14
29
1
2
18
18
11
19
2
1
28
15
6
11
5
5
23
2
23
1
27
15
20
6
6
16
26
8
17
10
3
11
26
23
14
13
15
21
10
19
4
14
15
16
14
19
24
6
11
28
10
20
1
2
5
11
1
1
10
Check input and AC output for thousands of problems on uDebug!

Ahmad93
New poster
Posts: 6
Joined: Wed Mar 05, 2014 6:39 pm

Re: 10608 - Friends

Post by Ahmad93 » Tue Apr 08, 2014 10:32 am

A lot of thanks to you brianfry713. Got accepted. :D

himagra
New poster
Posts: 1
Joined: Sun May 24, 2015 6:53 pm

Re: 10608 - Friends

Post by himagra » Sun May 24, 2015 6:58 pm

Can anyone fix my code. It's showing runtime error :-

Code: Select all

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstdio>
using namespace std;

vector<int> adj[1000];
vector<bool> visited(1000, false);
int tmp;

void dfs(int u)
{
    if(visited[u])
        return;

    visited[u] = true;
    tmp++;
    for(int i = 0; i < int(adj[u].size()); i++)
    {
        int v = adj[u][i];
        dfs(v);
    }
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n >> m;
        while(m--)
        {
            int x,y;
            cin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        int max = 0;
        
        for(int i = 1; i <= n; i++)
        {
            tmp = 0;
            visited.resize(1000,false);
            dfs(i);
            if(tmp > max)
                max = tmp;
        }
        cout << max << '\n';
    }
}

siam_cr7
New poster
Posts: 1
Joined: Thu Sep 10, 2015 1:42 pm

Re: 10608 - Friends

Post by siam_cr7 » Thu Sep 10, 2015 3:12 pm

For those who are having problem in finding out the correct algorithm, the given sample i/o is wrong.
see http://www.udebug.com/UVa/10608 for the correct i/o.

hope it helps. :)

Post Reply

Return to “Volume 106 (10600-10699)”