## 459 - Graph Connectivity

Moderator: Board moderators

ahmed hasan
New poster
Posts: 9
Joined: Fri Jan 21, 2005 5:09 pm

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

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;
}``````
Last edited by ahmed hasan on Tue Feb 15, 2005 7:21 am, edited 1 time in total.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi
if u use dfs algorithm then it will be faster than ur algorithm

MAP

Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:
Ghust_Omega , I owe you one !

ahmed hasan
New poster
Posts: 9
Joined: Fri Jan 21, 2005 5:09 pm
mohiul alam prince wrote:Hi
if u use dfs algorithm then it will be faster than ur algorithm

MAP
accepted

mshashi
New poster
Posts: 5
Joined: Sat Jul 31, 2004 1:35 pm
Location: IIT Kanpur
Contact:

### 459 RTE

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;
}
``````
Try try try ........... again

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
Could anyone post here more test cases??!!

keep it real!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 459 - Graph Connectivity

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..
``````
Last edited by helloneo on Tue May 22, 2007 8:07 am, edited 2 times in total.

Oh Se Jun
New poster
Posts: 2
Joined: Mon Jan 16, 2006 6:28 am

### 459 Graph Connectivity .. WA

Code: Select all

``````Acc..

Thank you
``````
Last edited by Oh Se Jun on Mon Feb 13, 2006 12:30 pm, edited 2 times in total.

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

### Hmm

Why don't you make big array size?

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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

Oh Se Jun
New poster
Posts: 2
Joined: Mon Jan 16, 2006 6:28 am
Yes..

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

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
Why WA?
!?!?!?

Code: Select all

``AC``
Last edited by IRA on Mon Feb 13, 2006 11:58 am, edited 1 time in total.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
Why WA?
!?!?!?

Code: Select all

``have AC.``

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

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

한국사람이군하...

web.humoruniv.com

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

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

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

### 459 R.E sigsev

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.
We the dreamer of the dreamy dream...