459 - Graph Connectivity

[ahmed hasan]

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;
}

[mohiul alam prince]

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

MAP

[Ali Arman Tamal]

Ghust_Omega , I owe you one !

[ahmed hasan]

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

MAP

accepted

[mshashi]

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;
}

[jaracz]

Could anyone post here more test cases??!!

Thx in advance

[helloneo]

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..

[Oh Se Jun]

Code: Select all

Acc.. 

Thank you

[tmdrbs6584]

Why don't you make big array size?

[Ghust_omega]

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]

Yes..

my answer quite right

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

[IRA]

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

Code: Select all

AC

[IRA]

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

Code: Select all

have AC.

[Psyco]

한국사람이군하...

web.humoruniv.com

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

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

[tuman]

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.