Page 3 of 9

### 459-graph connectivity: got TLE (accepted)

Posted: Sun Jan 30, 2005 5:57 am
How can I make this faster?
PLZ help.

Code: Select all

``````#include<stdio.h>
#include<string.h>
#define max 100
int set[max];
int cc;

int rootof(int node)
{
while(set[node]>0) node=set[node];
return node;
}

void setunion(int pr,int cr)
{set[pr]+=set[cr];  set[cr]=pr;}

void disjointset(int v1, int v2)
{
int r1=rootof(v1);
int r2=rootof(v2);

if(r1!=r2)
{
if(set[r1]<set[r2])
{setunion(r1,r2); if(v1!=r1)set[v1]=set[v2]=r1;}

else
{setunion(r2,r1); if(v2!=r2)set[v1]=set[v2]=r2;}

cc--;
}
}

void initgrp(int n)
{
int c1;
for(c1=0;c1<n;c1++) set[c1]=-1;
cc=n;
}

int main()
{
char ips[3];
int f=0;
while(1)
{
gets(ips);

if(ips[0]==' ')
{if(f)printf("%d\n",cc);break;}

if(strlen(ips)==1)
{
if(f)printf("%d\n",cc);
initgrp(ips[0]-'A'+1);
if(!f)f=1;
}

else if(strlen(ips)==2)
disjointset(ips[0]-'A',ips[1]-'A');
}
return 0;
}``````

Posted: Wed Feb 02, 2005 3:13 pm
Hi
if u use dfs algorithm then it will be faster than ur algorithm

MAP

Posted: Mon Feb 07, 2005 5:16 am
Ghust_Omega , I owe you one !

Posted: Fri Feb 11, 2005 4:57 pm
mohiul alam prince wrote:Hi
if u use dfs algorithm then it will be faster than ur algorithm

MAP
accepted

### 459 RTE

Posted: Sun Jul 03, 2005 1:31 pm
I am getting runtime error (SIGSEGV) in problem 459. I have checked it for all possible cases, but still I haven't been able to locate the problem. Can anyone please help me out ?

Here is the code :

Code: Select all

``````#include <iostream>
#include <vector>
#include <deque>
#include <string>
using namespace std;

int main(void){
int n;
cin >> n;
char max;
cin >> max;
for (int i = 0; i < n; i++){
int maxNodes = max - 'A' + 1;
//Read the edges from the input
vector < vector<int> > graph;
graph.reserve(maxNodes);
string in;
while(true && cin >> in){
if (in.length() == 1){
max = in[0];
break;
}
else{
int from = in[0] - 'A';
int to = in[1] - 'A';
graph[from].push_back(to);
graph[to].push_back(from);
}
}

bool visited[26];
for (int j = 0; j < maxNodes; j++)
visited[j] = false;

int parts = 0;

while (true){
int left = -1;

for (int j = 0; j < maxNodes; j++){
if (!visited[j]){
left = j;
break;
}
}
if (left == -1) break;
parts ++;
deque <int> dfs;
dfs.push_front(left);
while (!dfs.empty()){
int current = dfs[0];
dfs.pop_front();
visited[current] = true;
int len = graph[current].size();
for (int j = 0; j < len; j ++)
if (!visited[graph[current][j]]) dfs.push_front(graph[current][j]);
}

}
cout << parts << endl << endl;
}
return 0;
}
``````

Posted: Thu Sep 01, 2005 12:57 am
Could anyone post here more test cases??!!

### 459 - Graph Connectivity

Posted: Wed Jan 25, 2006 10:33 am
i'm trying to solve this problem with Union Find .. but i got RTE..
plz help me.. T.T

Code: Select all

``````maybe parsing error..
``````

### 459 Graph Connectivity .. WA

Posted: Sat Feb 11, 2006 8:43 pm

Code: Select all

``````Acc..

Thank you
``````

### Hmm

Posted: Sun Feb 12, 2006 11:21 am
Why don't you make big array size?

Posted: Sun Feb 12, 2006 7:48 pm
Hi!! Oh Se Jun I post some tests cases in a previous post, did you saw that post ?
http://online-judge.uva.es/board/viewtopic.php?t=6354

Posted: Mon Feb 13, 2006 4:22 am
Yes..

I can't understand what is wrong.. >.<

Posted: Mon Feb 13, 2006 11:44 am
Why WA?
!?!?!?

Code: Select all

``AC``

Posted: Mon Feb 13, 2006 11:44 am
Why WA?
!?!?!?

Code: Select all

``have AC.``

### &#54616;&#54616;&#54616;

Posted: Tue Feb 21, 2006 2:31 pm
한국사람이군하...

web.humoruniv.com

웃긴대학에 다니는 형을 몰라보다니...ㅋㅋ

굴다리 밑으로 10초안에 와라!

### 459 R.E sigsev

Posted: Thu Apr 06, 2006 1:46 pm
plz help me to understand where the problem is occuring, every time i hv tried to do it i recieved R.E sigsev. Is it related with newline problem????

plz run my code :

#include<stdio.h>
#include<string.h>
#include<math.h>
long I,J,K,A[51][51],i1,i2,count=0,que[51],orig[52],q,i,j,k;
long tuti,futi,avail=0,vn=0,org,front,rear,mue[51];
long chinu,minu,kuti,remain[51],cnt,cmt;
char c1,c2,c3,c4,letter,ab[100],ch,nd;
long b,c,d,e,rmn,f,node,test,tst;
long n1,n2;
void main()
{scanf("%ld",&test);
printf("\n");
scanf("%c",&ch);
for(tst=1;tst<=test;tst++)
{
futi=0;tuti=0;kuti=0;
while(1)
{
scanf("%c",&c1);
if(c1=='\n')
break;
else if(c1!=' ')
letter=c1;
}
node=letter-64;
while(1)
{
cnt=0; cmt=0;
while(1)
{
scanf("%c",&c2);
if(c2=='\n')
break;
else if(c2!=' ')
{ if(cmt==0)
{c3=c2;cmt=1;}
else
c4=c2;
}

}

if(cmt==0)
break;
else
{

A[c3-64][c4-64]=1;
A[c4-64][c3-64]=1;
remain[c3-64]=1;
remain[(c4-64)]=1;

}

}
for(rmn=1;rmn<=node;rmn++)
{
if(remain[rmn]==1)
remain[rmn]=0;
else
futi++;
}
//printf("\n");
kuti=0;
for(I=1;I<=node;I++)
{
chinu=0;
for(K=1;K<=kuti;K++)
{
if(I==mue[K])
{chinu=1;break;}
}
if(chinu==0)
{ front=1;
rear=1;

kuti++;
que[1]=I;
mue[kuti]=I;
org=0;
tuti=0;
while(1)
{
avail=0;
vn=0;
i=que[front];

for(j=1;j<=node;j++)
{
if(A[j]==1)
{
for(k=1;k<=rear;k++)
{if(j==que[k])avail=1;}

if(avail==0)
{

tuti++;
rear++;
kuti++;
que[rear]=j;
mue[kuti]=j;

}

avail=0;

}

}

if(que[front]==0)
{
if(tuti>0)
futi++;
break;
}
front++;
}
for(J=1;J<=node;J++)
que[J]=0;

}

}

for(i=0;i<=node;i++)
for(j=0;j<=node;j++)
A[j]=0;

printf("%ld\n",futi);
if(tst<test)
printf("\n");

for(J=1;J<=node;J++)
{ que[J]=0;
mue[J]=0;

}

}

}

plz give me some i\o to justify my problem.