315 - Network

[CodeMaker]

hi, a few minutes ago i got accepted using another approch that i think is inefficient. that points to 2 things -> either my previous algo is wrong or that doesn't cover the special cases. i m now trying to figure it out, but if anyone can point mistake in my posted code....plz let me know. thanks in advance

[CodeMaker]

Ok, i found out what is wrong with my previous code. it doesn't cover all cases.

Code: Select all

input:
5
0
0
output:
5

[Faisal_Bd]

Dear Jalal,
Is that output correct? I think the correct output is 0. What is your output by the accepted solution?

[CodeMaker]

Hi, for this problem, the output is correct. because of this case my previous code got wrrong answer. this output is from my Acc code. and i wrote my new code with considering this type of case specially, and it got Accepted. the graph may be disconnected. may be u should not call this problem an articulation point problem- that will make things easy.

[Faisal_Bd]

The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.

If your output (5) is correct, let me say something! The graph of your input consists of 5 vertices and no edges. right? so power supply failure of one place can affect no other place. Then how can it be critical? According to the problem discussion, in order to be critial, a place must cause failure of power supply of some other places if its power supply goes down.

I expect more discussion on this problem from the GURUs. Hope they will say something to remove this confusion....

[CodeMaker]

i had the same question in my mind. but when i got wrong answer, i checked for disconnectivity in the input graph. there are many problem which is confusing and i dont think there is anything to discuss about this type of problem, becasuse this problem is made in this way. lets forget it. u have to solve it considering a specific approch.

[Faisal_Bd]

I also considered disconnected graph. But I didn't consider the "ambiguous case" mentioned above. Now I am trying to fix (??) it accordingly. Thanks for your help, dear Jalal!

[Faisal_Bd]

Dear Jalal, your solution is wrong! The problem description is absolutely right. It is a problem of finding articulation point.

For your input, the output is 0.

Oh !!!!! got AC doing just one change! I did mistake in taking input. It's so silly mistake! shame! Given N, if N number of lines follow, then input was terminated for that graph. My program didn't consider the ending '0' as the marking of end of the block. Rather it considered this ending '0' as the new input!

Ah.... this silly mistake kept me mad for one week!

Now I can look for solving the next problem - 796 (Critical Links)

[CodeMaker]

thats strange!!! my previous code was correcrly written from psudocode and i checked it over and over. but still i got wrong answer. then i cosidered that the graph may be disconnected and i wrote my code in a bruteforce approch where i block a single node at a time and check if the graph is disconnected then i consider it an articulation point and it got accepted. there is no problem in my input i think, because i used the same input part in both of my code. i just changed the disconnectivity part

[matys]

Hi I wrote code but I receive Wa...I found some tests on forums and my program pass all of them. Here is my code:

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
int d[101][101],num[101],p[101],l[101],ti,r[101];
void vis(int u,int f,int n){
    int num1=0,num2=0;
    p[u]=f;
    num[u]=ti++;
    l[u]=num[u];
    for(int i=1;i<=n;i++)
    if(d[u][i])
        if(i!=f){
            if(num[i]==-1){
                vis(i,u,n);
                l[u]=min(l[u],l[i]);
            }
            else
            l[u]=min(l[u],num[i]);
        } 
}           
void dfs(int n){
    for(int i=1;i<=n;i++)num[i]=-1;
    for(int i=1;i<=n;i++)p[i]=-1;
    ti=1;
    for(int i=1;i<=n;i++)
    if(num[i]==-1)
    vis(i,-1,n);
} 
void calc(int n){
    int i,j;
    for(i=1;i<=n;i++){
        if(p[i]==-1){
            int il=0;
            for(j=1;j<=n;j++)if(d[i][j])il++;
            if(il>1)r[i]=1;
        }
        else{
            int il=0;
            for(j=1;j<=n;j++)
            if(l[j]>=num[i]&&d[i][j])il++;
            if(il)r[i]=1;
        }
    }
}                   
main()
{
  int i,u,v,n,ile,j,c;
  while(1){
      if(scanf("%d",&ile)!=1)break;
      if(ile==0)break;
      for(i=0;i<=ile;i++)
      for(j=0;j<=ile;j++)d[i][j]=0;
      for(i=0;i<ile;i++){
          scanf("%d",&u);
          if(!u)break;
          while(1){
               if((c=fgetc(stdin))=='\n')break;
               else if(c==' ')continue; 
               else ungetc(c,stdin);
               scanf("%d", &v); 
               d[u][v]=d[v][u]=1;
           }
       }
       for(i=1;i<=ile;i++)r[i]=0;
       dfs(ile);
       calc(ile);
       int res=0;
       for(i=1;i<=ile;i++)if(r[i])res++;
       printf("%d\n",res);
   }            
  return 0;
}

Can anybody help me??

[david]

Finally, about one year later, I managed to find out what was wrong with my code... When reading the adjacency list, I never read more lines than the number of vertices of the graph.

[Ahmed_Hasan]

getting WA

i tried my prog with the following IO



input

Code: Select all

8
2 4 5
1 3
2 4 7
1 5 6 8 7 3
1 4 6
5 4 8
3 4
4 6
0

8
2
1 3
2 4 5 6
3 7 8
3
3
4 8
4 7
0

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0

5
2
3
4
5
0

5
2 3 4 5
3 1
2 1
1 5
1 4
0

6
2 3
1 4
1 4 5
2 3 6
3 5
4 5
0

9
1 2
2 3
2 5
5 4 6 8 
7 8
9 8
0

3
1 2
3 2
0
2
2 1
0

3
2
3
0


6
2 3
1 4
1 4 5
2 3 6
3 6
4 5
0

5
3 2
1 3
1 2 4 5
3 5
3 4
0

output

Code: Select all

0
3
1
2
3
1
0
4
1
0
1
0
1

need some more IO

the articulation points found by my prog for the graphs are

Code: Select all

Number of Articulaion point=0

2 3 4 
Number of Articulaion point=3

1 
Number of Articulaion point=1

1 2 
Number of Articulaion point=2

2 3 4 
Number of Articulaion point=3

1 
Number of Articulaion point=1


Number of Articulaion point=0

2 3 5 6 
Number of Articulaion point=4

2 
Number of Articulaion point=1


Number of Articulaion point=0

2 
Number of Articulaion point=1


Number of Articulaion point=0

3 
Number of Articulaion point=1

[bijon]

correct your output pattern and check your input patter.i am sure that your code is correct.why?because my code is same

[SDiZ]

I can't understand the test-cases posted above.....

Can any one tell me why the test case:

Code: Select all

5 
3 2 
1 3 
1 2 4 5 
3 5 
3 4 
0

have the output

Code: Select all

1

Code: Select all

3 
Number of Articulaion point=1

I think there is no articulaion points !
see :


After removing point 3, the graph is still connected.
Have I mis-understood the question?

[smap16501004]

why

Code: Select all

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int node;
bool W[100][100];
bool mark[100];
int drop;
void check(int in)
{
    int j;
    mark[in]=1;
    for(j=0;j<node;j++)
        if(drop!=j && W[in][j] && !mark[j])
            check(j);
    
}

int main(void)
{
    
    char x[100];
    char * pch;
    bool t;
    int from,to,i,j,count;
    
    while(cin>>node && node!=0)
    {
        cin.get();
        for(i=0;i<node;i++)
            for(j=0;j<node;j++)
                W[i][j]=0;
        while(cin.getline(x,100))
        {
            pch=strtok(x," ");
            from=atoi(pch);
            if(from==0)break;
            pch=strtok(NULL," ");
            while(pch!=NULL)
            {
                to=atoi(pch);
                W[from-1][to-1]=1;
                W[to-1][from-1]=1;
                pch=strtok(NULL," ");
                
            }
            
        }
        count=0;
        for(drop=0;drop<node;drop++)
        {
            for(j=0;j<node;j++)
                mark[j]=0;
            check((drop+1)%node);
            t=1;
            for(j=0;j<node;j++)
                if(drop!=j && !mark[j])t=0;
            if(t)
                count++;
        } 
        cout<<node-count<<endl;
    }
    
    return 0;
}