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

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### hello, i'm new here, just solved 315

hello everyone,

i'm a depressed loser and found this site as i was looking for programming challenges/wargames on the internet... this site is very cool, there are a lot of problems too hehe
after a first tryon problem 315, i found out my program was too slow, and redesigned it almost entirely, and then it worked
it wasn't really hard, but for a depressed loser it's quite cool.

feel free to msg me there: apoptose at free dot fr

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### 315: Network

Could someone tell me if there's any trick in this problem. I can't figure out why I get WA. My approach is quite simple, I pick up one vertex at a time and see if it the graph remains connected without that vertex. If "No", I increase my cut vertex counter.

I found the following test case for which my solutiong gives 8 as answer, but the output file along with the case says 7!
17
1 14 11
6 7
10 15
8 10 15
14 11 1
9 7 12
3 1
7 12
4 8
13 17 7
17 6
5 11
11 8
2 5
16 9
15 17
0
0
My solution takes the following 8 vertices as cut vertices:
1, 5, 7, 8, 9, 11, 15, 17
Could someone point out my mistake?

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
Ignore the previous post.
I got AC.
The output for the test file I had, itself was wrong.

davidsu
New poster
Posts: 3
Joined: Fri Jan 31, 2003 10:02 am
I got WA too,I got 8 with kmhasan's test case,could anyone give me more test case?

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Hi davidsu, 8 is the right answer. You can try these inputs:
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
0
And the answers should be:
3
1
0
Good luck!

babor
New poster
Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm
Contact:
Reda the new problem description.
babor

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### 315 : Network - How to get a better timing?

I've solved q315 using repeated Breadth First Search with a subset of the network. My timing was 1.1seconds..

I saw on the listing that there are people who managed a cool 0.2 seconds.. Can anyone tell me how to go about achieving that?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
this is problem of finding articulation points in graph, which can be solved by running DFS once. try search in google about articulation points or you also can find it in CLR.
Kalo mau kaya, buat apa sekolah?

Opexoc
New poster
Posts: 2
Joined: Tue Jul 06, 2004 4:57 pm
Location: Poland
Contact:

### small problem 315

I have small problem with reading data on input.
I am writing program in c++ language but i don't know how i could write
operation of reading data for this problem. Program should read numbers while it doesn't see end of line. How i could implementate this in c++ ?

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Can anyone tell me what's wrong with my program?
It prints the correct answer for every input I have tried, but gives WA after 0.000 s, so I thought the problem might be input-related and added some extra checking (i.e, white spaces at the end of the line or cheking end of input file), but to no avail.

[c]
/* 315 network */
#include <stdio.h>
#include <string.h>

#define maxtam 110
#define infinito 2000000

char conect[maxtam][maxtam];
int numact, numv, tiene2, numart;
int desc[maxtam];

int dfs(int v, char esraiz) {
int n, m, d, i, h, menor;

h = numact;
desc[v] = numact--;
m = -1;
i = 0;
menor = infinito;
for (n = 0; n < numv; n++)
if (conect[v][n]) {
if (desc[n]) {
if (desc[n] > m)
m = desc[n];
} else {
d = dfs(n, 0);
if (d > m) m = d;
if (d < menor) menor = d;
i++;
}
}
if (esraiz && i >= 2) tiene2 = 1;

if (!esraiz && menor <= h)
numart++;

return m;
}

int main() {
int n, a, b, numar, c;

for (;;) {
memset(conect, 0, sizeof(conect));

if (scanf("%u", &numv) != 1) break;
if (!numv) break;
for (n = 0; n < numv; n++) {
scanf("%u", &a);
if (!a) break;
a--;
for (;;) {
if ((c = fgetc(stdin)) == '\n') break;
else if (isspace(c)) continue;
else ungetc(c, stdin);

scanf("%u", &b);
b--;
conect[a] = conect[a] = 1;
/* printf("%u %u\n", a, b);*/
}
}
numact = numv;
numart = 0;

memset(desc, 0, sizeof(desc));
tiene2 = 0;
dfs(0, 1);

if (tiene2) numart++;
printf("%u\n", numart);
}
return 0;
}
[/c]

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:

Code: Select all

``````1
0``````
the output should be

Code: Select all

``0``
one more case:

Code: Select all

``````0
0
0
0``````
output:
(nothing, program is supposed to terminate)

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
My program works fine for both inputs. Might the problem statement be wrong? For example, might the judge test data contain disconnected graphs or graphs with more than 100 vertices?
Last edited by david on Fri Sep 30, 2005 11:38 pm, edited 1 time in total.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
Same here. My code worked for all test cases I have created and tseted. I am at my wit's ends

Code: Select all

``````#include <stdio.h>
#include <string.h>

typedef struct{
int cnt;
int vertex[105];

int i,n,p,q,time,total;
int visit[105];
int low[105], pre[105], discover[105];
int pts[105];
char str[1000];

int min(int a, int b){
if (a < b)
return a;
return b;
}

void DFS(int v){
int ii,w;
visit[v] = 1;
low[v] = discover[v] = ++time;
for (ii=0;ii<list[v].cnt;ii++){
w = list[v].vertex[ii];
if (visit[w] == 0){
pre[w] = v;
DFS(w);
low[v] = min(low[v],low[w]);
}else if (w != pre[v]){
low[v] = min(low[v],discover[w]);
}
}
return;
}

void articulationpts(){
int jj,w,v;
for (v=1;v<=n;v++){
if (pre[v] == 0){ /*root*/
if (list[v].cnt > 1)
pts[v] = 1;
}else{
for (jj=0;jj<list[v].cnt;jj++){
w = list[v].vertex[jj];
if (low[w] >= discover[v])
pts[v] = 1;
}
}
}
return;
}

void addvertex(int a, int b){
int ii;
for (ii=0;ii<list[a].cnt;ii++)
if (list[a].vertex[ii] == b)
return;
list[a].vertex[ii] = b;
list[a].cnt++;
return;
}

int main(){
char *pch;
while (scanf("%d ",&n)!=EOF){
if (n == 0)
break;
memset(list,0x0,sizeof(list));
memset(visit,0x0,sizeof(visit));
memset(discover,0x0,sizeof(discover));
memset(pre,0x0,sizeof(pre));
memset(low,0x0,sizeof(low));
memset(pts,0x0,sizeof(pts));
total = 0; time = 0;
while (gets(str)!=NULL){
pch = strtok(str," ");
sscanf(pch,"%d ",&p);
if (p == 0)
break;
pch = strtok(0," ");
while (pch!=NULL){
sscanf(pch,"%d ",&q);
/*Bi-directed graph*/
pch = strtok(0," ");
}
}
for (i=1;i<=n;i++){
if (visit[i] == 0)
DFS(i);
}
articulationpts();
for (i=1;i<=n;i++){
if (pts[i] == 1)
total++;
}
printf("%d\n",total);
}
return 0;
}
``````

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

### 315 - Network

Can anybody please help me me with some input and output? I have tried this problem but have got WA. It's a problem of finding articulation point, isn't it? Is there any tricky test case?

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
``````Accepted