459 - Graph Connectivity

[serur]

Hello Fellows!

The Problem is in 459-"Graph Connectivity". OJ responds "WA".
The problem is in finding how many connected componentns are there in given non-oriented graph, isn't it? Then it can be solved by DFS?
My algo:
after parsing input I run a loop from 'A' to the "the largest node name in the graph" and for every symbol(node of a graph) check whether it is visited or not. If not visited, I increment component_counter by 1 and floodfill the connected component.
Also, how should one benefit if uses solution based on Disjoit-Set data structure instead of DFS?

[helloneo]

Hello Fellows!

The Problem is in 459-"Graph Connectivity". OJ responds "WA".
The problem is in finding how many connected componentns are there in given non-oriented graph, isn't it? Then it can be solved by DFS?
My algo:
after parsing input I run a loop from 'A' to the "the largest node name in the graph" and for every symbol(node of a graph) check whether it is visited or not. If not visited, I increment component_counter by 1 and floodfill the connected component.
Also, how should one benefit if uses solution based on Disjoit-Set data structure instead of DFS?

You're algo seems to be alright.. don't know why WA ..
and "Union-Find" is maybe faster than DFS..

I got TLE for the problem "793 - Network Connections " with your algorithm.. but I re-coded with "Union-Find" and then I got AC..

[serur]

Thank you Helloneo for your reply!
The problem was in assuming that input is nicely formatted, it's so stupid of me to be trapped in such a way! Now AC.
Well, I should think about Union-Find, its implementation and elaboration.
Thank you!

[Jan]

Edit : I have to look it again.

[yin_yang2k]

I am getting WA on this problem. Can someone with a AC code try the input on the next post and share the result with us who needs it ?
My code is generating 2 new lines when it outputs the last case, could that be the error?
[edit](code link removed, got accepted)[/edit]
I'm new to C++ and just learned about that you have to delete objects that you create. (Witch you don't have to in Java)

[yin_yang2k]

Please post your result for this input. (If you have a AC code that is )

INPUT

Code: Select all

10

E  	
	AB          
     CE         
  	  DB 			
	   EC   		

Z
AB
CF

A
ZY
WS
PQ

D
AA
BB
CC
DD

E
AB
BA
AB
BA

Z
AB
BC
CD
DE
EF
FG
GH
HI
IJ
JK
KL
LM
MN
NO
OP
PQ
QR
RS
ST
TU
UV
VW
WX
XY
YZ

A

M

Z

I
AI
BI
CI
DI
IE
IF
IG
IH

My WA code output, and yes those two new lines at the end is something my code does.
[edit] got Accepted and I still get this output, (removed the last new line because it gave PE) [/edit]

Code: Select all

2

24

1

4

4

1

1

13

26

1

[Ghust_omega]

Hi !! yin_yang2k

I will go to post mi algorithm for take the input cause the algorithm for get the answer is easy, is just take the components conex.

Code: Select all

int read_graph(graph *g)
{
	int i,j,p,x,y,res1;
	char c[10],*res2;//this is for take the input
	
	initialize_graph(g);//fluhs the graph
	gets(c);//get the line 
	sscanf(c,"%c",&c[0]);//I scan for the firts caracter
	i = c[0]-'A';
	g->nvertices = i+1;
	
	for(j=0;j<i+1;j++)
		visited[j]=false;
	p=0;
	while(1){
		res2=gets(c);
		res1=sscanf(c,"%s",c);
		if(res1==EOF || res2==NULL)//if there is nothing break
			break;
		x = (int)(c[0] - 'A');//see the node origin
		y = (int)(c[1] - 'A');//see the destiny
		insert_edge(g,x,y,0);//insert edge in the graph
	}
	return 1;
}

Hope that helps
Keep posting

[Ghust_omega]

by the way your ouput is fine my program give the same answers

Hope it helps
Keep Posting

[yin_yang2k]

Thanks Ghust_omega!

I remade my input algorithm to look like yours and I got Presentation Error (Accepted). Then after some work with the new lines in my output algorithm I got accepted. I didn't touch my algorithm that solves the problem so it was al about the input algorithm.

I often have problem with the input and output with C++. Is there a thread in the forum about how to read input in C++ ?
I hope UVA will get a newer Java version soon

tnx again!

[Ghust_omega]

Hi !! yin_yang2k

Is good see that your problem is fine, for the problems of the input in c++ I used a mix between C and C++ for the read input because I consider that C has better read and out that C++, sometimes is uncorfortable write cout<< and << and <<...... etc. but is a opinion very personal, so I use C for the input and C++ for code the rest. Here in the board you can find a chapter dedicated to C++ see if there any topic about the input.

Hope it helps
Keep posting

[smilitude]

My main function looks like this, I used union-find data struct;

Code: Select all

int main() {
    int cases;
    int i,j;
    char line[1000];
    bool check[30];
    char ch,a,b;
    int n;
    int count;
    bool print=false;
    int len;
    
    cin>>cases;
    cin.getline(line,255);
    cin.getline(line,255); //garbage
    while(cases--) {
        cin>>ch;
        cin.getline(line,255); //garbage
        n=ch-'A';
        for(i=0;i<=n;i++) makeset(i);
        memset(check, false , sizeof(check));
        count=0;
        while(true) {
            cin.getline(line,255);
            if(!strcmp(line,"")) break;
            len=strlen(line);
            for(i=0;i<len;i++) 
                if(line[i]>='A' && line[i]<='Z') {
                    a=line[i];
                    i++;
                    break;
                }
            for(;i<len;i++)
                if(line[i]>='A' && line[i]<='Z') {
                    b=line[i];
                    break;
                } 
                
            setunion(a-'A',b-'A');
        }
        for(i=0;i<=n;i++) 
            check[p[i]]=true;
        for(i=0;i<=n;i++) 
            if(check[i]) count++;
        if(print) cout<<endl;
        cout<<count<<endl;
        print=true;
    }
//system("pause");
return 0;
}

This works fine for all the IO in this thread, but still WA.
May I ask for some IO, or some suggestion plz?

[tuman]

After a long time
Sorry jAn it didnt solve the matter. Still run time error. This time your prediction didnt click. Why dont u ve another look at it? I hv done this typo of problem b4. But i guess i ve some problem in taking input here.

[l314]

Hi,I get WA all the time, I don't know why!!

I have tried all the input cases of below threads.
(my code got the the same output)
http://online-judge.uva.es/board/viewto ... 7467f8212e
http://online-judge.uva.es/board/viewto ... d76eef7fe2

My source:

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int turn, size, n1, n2, ans;
    char node1,node2;
    string c;
    string read;
    bool visted[26]={0};
    
    cin>>turn;
    cout<<endl;
    while(turn--){
       ans = 0;
       cin>>c;
       cin.ignore();
       size = c[0] - 'A'+1;
       bool table[size][size];
       bool flag;
       
       for(int i=0; i<size; i++)
          for(int j=0; j<size; j++)
             table[i][j] = false;
       
       while(1){               
          getline(cin, read);
          read.erase(remove(read.begin(), read.end(), ' '), read.end());
          
          if( read.empty() == true || read[0] == '\0')
              break;
          n1 = read[0] - 'A';
          n2 = read[1] - 'A';
          if(n1 != n2){
             table[n1][n2] = true;             
             table[n2][n1] = true;
          }   
       }
       
       for(int i=0; i<size; i++){
          flag = false;     
          for(int j=0; j<size; j++){
              if(table[i][j] == true){
                  if(visted[j] == true)
                     flag = true;
                  else   
                     visted[j] = true;          
              }                     
          }
          if(visted[i] == false && flag == false)
              ++ans;
       }
       
       cout<<ans<<endl; 
       cout<<endl;
       for(int i=0;i<size;i++)
          visted[i]= false;                        
    }
   return 0;                 
}

plz help me, thx.

[rio]

Your algorithm is wrong. Consider this case.

Code: Select all

1

E
AE
EC
CB
BD

This graph is

Code: Select all

A - E - C - B - D

but your code answers 2.

Your output format is wrong too.

The outputs of two consecutive cases will be separated by a blank line.

Don't print a blank line before the first case, and after the last case.
----
ADD : Don't open a new thread if it already exist for the problem.

[l314]

Hi, I fixed my algorithm so that it can output correctly for your input case and all cases from below links, but I still get WA.
http://online-judge.uva.es/board/viewto ... 7467f8212e
http://online-judge.uva.es/board/viewto ... d76eef7fe2

Thank for your help.

My new source:

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int turn, size, n1, n2, ans, max;
    char node1,node2;
    string c;
    string read;
    bool visted[26]={0};
    
    cin>>turn;
    while(turn--){
       ans = 0;
       cin>>c;
       cin.ignore();
       size = c[0] - 'A'+1;
       bool table[size][size];
       
       for(int i=0; i<size; i++)
          for(int j=0; j<size; j++)
             table[i][j] = false;
       
       while(1){               
          getline(cin, read);
          read.erase(remove(read.begin(), read.end(), ' '), read.end());
          
          if( read.empty() == true || read[0] == '\0')
              break;
          n1 = read[0] - 'A';
          n2 = read[1] - 'A';
          if(n1 != n2){
             if(n1 > n2)
                table[n1][n2] = true;
             else
                table[n2][n1] = true;
          }   
       }
       
       for(int i=1; i<size; i++){   
          for(int j=0; j<i; j++){
              if(table[i][j] == true){
                  if(visted[j]==true)
                     visted[i] = true;
                  else                
                     visted[j] = true;          
              }                     
          }
       }
       
       for(int i=0; i<size; i++){
          if(visted[i] == false)
             ++ans;        
       }
          
       if(ans == 0)
          ++ans;
       cout<<ans<<endl; 
       if(turn != 1)
          cout<<endl;
       for(int i=0;i<size;i++)
          visted[i]= false;                        
    }
   return 0;                 
}