459 - Graph Connectivity
Moderator: Board moderators
-
- New poster
- Posts: 7
- Joined: Wed Dec 12, 2001 2:00 am
- Location: Bangladesh
-
- New poster
- Posts: 7
- Joined: Wed Dec 12, 2001 2:00 am
- Location: Bangladesh
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
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![:smile:](./images/smilies/icon_smile.gif)
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
![:smile:](./images/smilies/icon_smile.gif)
ACM 459
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]
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]
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]
[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]
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]
"Everything should be made simple, but not always simpler"
so then how does the input work in this case?
ok, the non-specified multiple input is giving me a hard time again...
am I right that the input looks something like this?
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!
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
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
-
- New poster
- Posts: 4
- Joined: Sat Nov 23, 2002 2:00 pm