315 - Network

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

Moderator: Board moderators

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Sep 26, 2005 7:51 am

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 :)
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Sep 26, 2005 7:44 pm

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

Code: Select all

input:
5
0
0
output:
5
Jalal : AIUB SPARKS

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Wed Sep 28, 2005 11:28 am

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Sep 28, 2005 12:09 pm

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. :)
Jalal : AIUB SPARKS

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Wed Sep 28, 2005 12:23 pm

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Sep 28, 2005 12:42 pm

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. :evil: lets forget it. u have to solve it considering a specific approch. :x
Jalal : AIUB SPARKS

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Wed Sep 28, 2005 12:50 pm

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
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Wed Sep 28, 2005 3:36 pm

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) :D

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Fri Sep 30, 2005 6:51 am

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 :o
Jalal : AIUB SPARKS

matys
New poster
Posts: 1
Joined: Sat Oct 08, 2005 12:53 pm

315

Post by matys » Sat Oct 08, 2005 12:56 pm

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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Tue Nov 15, 2005 12:47 am

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
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

315 getting WA

Post by Ahmed_Hasan » Sat Dec 03, 2005 5:35 pm

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
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Wed Feb 08, 2006 4:57 am

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

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

Post by SDiZ » Thu Jul 13, 2006 11:11 am

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 :
Image

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

smap16501004
New poster
Posts: 3
Joined: Thu Jul 27, 2006 4:32 pm

315 WA

Post by smap16501004 » Sat Jul 29, 2006 6:56 pm

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

Post Reply

Return to “Volume 3 (300-399)”