459 - Graph Connectivity

[bolster]

Are there any degenerate cases to worry about in this? I keep getting WA, for no apparent reason. Are there mysterious multiple test cases or something?

[FCS]

Are you using pascal?
This input file is screwed for pascal.
I only managed to get it accepted in C.

[bolster]

No, I'm using C... It's kinda funny... I got AC on 10178, so it's probably just some annoyingness that has been done to the input... Sometimes, it's all in one block, sometimes there's a space... completely inconsistent input *snicker*

[Yeamin Rajeev]

The judge input is really very annoying. I got accepted after making a lot of assumptions. Like this is valid input:

E
A B
C E
DB
E C

Yes, a lot of spaces may appear in input!!
Hope it can help.

[Yeamin Rajeev]

....And another assumption: Since one input block ends with an empty line and the prob is multiple input - one can easily guess two blank lines append each input block. But it's not right - only one blank line. Tricky, isn't it?

[junjieliang]

I don't think there are spaces. I use gets(s) and check s[0] and s[1], and I got ac.

[cyfra]

Hi.

I am writing in Pascal and I got accepted
( so I am sure that test case is not wrong)

Don't forget that it is multiple input problem !!!!!

So the input looks like this

number of test cases
- blank line
-first test
-blank line
.....

and the output
-first output
-blank line
- second output

In the input in the last test case you should read data until End Of File..

I have written such a program and it got accepted..

Good luck

[htl]

Why doesn't this code get accepted? It always gets time limit exceed.
I think it's the data reading problem
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
int matrix[30][30],record[30][30],count,n,visited[30];
void dfs(int);
void main(void)
{
int x,y,a,b;
char buffer[10],c;
scanf("%d",&x);
for(y=0;y<x;y++)
{
fflush(stdin);
scanf("%c",&c);
n=c-'A'+1;
for(a=0;a<n;a++)
for(b=0;b<n;b++)
matrix[a]=record[a]=0;
for(a=0;a<n;a++)
visited[a]=NO;
while(1)
{
fflush(stdin);
gets(buffer);
if(strlen(buffer)==0)
break;
matrix[buffer[0]-'A'][buffer[1]-'A']=matrix[buffer[1]-'A'][buffer[0]-'A']=1;
}
count=0;
while(1)
{
for(a=0;a<n;a++)
if(!visited[a])
break;
if(a==n)
break;
count++;
dfs(a);
}
printf("%d\n",count);
}
}
void dfs(int v)
{
int x;
for(x=0;x<n;x++)
if(matrix[v][x])
break;
visited[v]=YES;
for(;x<n;x++)
if(!record[v][x] && matrix[v][x])
{
record[v][x]=record[x][v]=count;
dfs(x);
}
}
[/c]

[henar2]

There is a problem with the input, the last line that the judge enters is data, not \n.

[htl]

How about this one? It got WA.
[c]
#include<stdio.h>
#include<stdlib.h>
int place[26],n;
void put(int,int);
int comp(const void*,const void*);
void main(void)
{
int count,x,y,a,b,ans;
char s[30],max;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
scanf("%c\n",&max);
n=max-'A'+1;
for(y=0;y<26;y++)
place[y]=-1;
for(y=0;y<n;y++)
place[y]=y;
while(gets(s)!=NULL)
{
if(!s[0])
break;
for(y=0;s[y]!='\0';y++)
if(s[y]>='A' && s[y]<='Z')
{
a=s[y]-'A';
break;
}
for(y++;s[y]!='\0';y++)
if(s[y]>='A' && s[y]<='Z')
{
b=s[y]-'A';
break;
}
if(place[a]!=place)
put(a,b);
}
qsort(place,n,sizeof(int),comp);
for(y=1,ans=1;y<n;y++)
if(place[y-1]!=place[y])
ans++;
printf("%d\n",ans);
}
}
void put(int i,int j)
{
int x,temp;
temp=place;
for(x=0;x<n;x++)
if(place[x]==temp)
place[x]=place[j];
}
int comp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
[/c]

[anupam]

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 50
int color[N],a[N][N],n;
char ch[N];
void dfs(int b)
{
	int i;
	color[b]=1;
	for(i=0;i<n;i++)
		if(a[b][i] && a[i][b] && (!color[i]))
			dfs(i);
}

main()
{
int m,i,j,z,l;
	gets(ch);
	m=atoi(ch);
	gets(ch);
	for(z=0;z<m;z++)
	{
		gets(ch);
		n=ch[0]-'A';
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				a[i][j]=0;
		while(1)
		{
			if(gets(ch)==NULL) break;
			if(!strcmp(ch,"")) break;
			a[ch[0]-'A'][ch[1]-'A']=a[ch[1]-'A'][ch[0]-'A']=1;
		}
		for(i=0;i<n;i++)
			color[i]=0;
		l=0;
		for(i=0;i<n;i++)
			if(!color[i])
			{
				l++;
				dfs(i);
			}
		if(l)
			printf("%d\n",l);
		else printf("1\n");
		if(z!=(m-1))
		 printf("\n");
	}
	return 0;
}[cpp]
will any1 help not getting wawa....?
greetings to all.
--Anupam :oops: [/cpp]

[zsepi]

ok, the non-specified multiple input is giving me a hard time again...
am I right that the input looks something like this?

Code: Select all

3
C
AB
BC
CA

D
AB
CD

E
AC
BD
EA

PS: in case the input has the above format - what is there any catch? I tested my code with cases I could think about, including repeated edges, slef-loops, etc., but something must be wrong... pls, help!

[rjhadley]

There should be a blank line after the 3:

3

C
AB
etc.

Have you tried an input with no edges? e.g.

1

D

[zsepi]

There should be a blank line after the 3:

that was the catch... thanx a lot!

[knightmare]

For an input with no edges, like this:

-------------------
1

B
-------------------

Should the output be the number of nodes (2 in this example)?