459 - Graph Connectivity

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

Moderator: Board moderators

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

459-graph connectivity: got TLE (accepted)

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Feb 02, 2005 3:13 pm

Hi
if u use dfs algorithm then it will be faster than ur algorithm

MAP

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

Post by Ali Arman Tamal » Mon Feb 07, 2005 5:16 am

Ghust_Omega , I owe you one :D !

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

Post by ahmed hasan » 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

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

459 RTE

Post by mshashi » 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{
        //Add this to the adjacency list
        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 :-)

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Thu Sep 01, 2005 12:57 am

Could anyone post here more test cases??!!

Thx in advance
keep it real!

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

459 - Graph Connectivity

Post by helloneo » 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..
already solved..
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

Post by Oh Se Jun » Sat Feb 11, 2006 8:43 pm

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.

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

Hmm

Post by tmdrbs6584 » Sun Feb 12, 2006 11:21 am

Why don't you make big array size?

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » 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 ?
if you dont, the link
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

Post by Oh Se Jun » Mon Feb 13, 2006 4:22 am

Yes..

my answer quite right

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

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Mon Feb 13, 2006 11:44 am

Why WA?
My answer is right....
!?!?!?

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

Post by IRA » Mon Feb 13, 2006 11:44 am

Why WA?
My answer is right....
!?!?!?

Code: Select all

have AC.

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

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

Post by Psyco » Tue Feb 21, 2006 2:31 pm

한국사람이군하...

web.humoruniv.com

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

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

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

459 R.E sigsev

Post by tuman » 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.
We the dreamer of the dreamy dream...

Post Reply

Return to “Volume 4 (400-499)”