Page 1 of 5
hello, i'm new here, just solved 315
Posted: Tue Nov 12, 2002 11:19 pm
by epsilon0
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
if you have any questions about this challenge, or reply on the board
315: Network
Posted: Tue Nov 26, 2002 8:02 pm
by kmhasan
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?
Posted: Tue Nov 26, 2002 9:02 pm
by kmhasan
Ignore the previous post.
I got AC.
The output for the test file I had, itself was wrong.
Posted: Fri Jan 31, 2003 10:07 am
by davidsu
I got WA too,I got 8 with kmhasan's test case,could anyone give me more test case?
Posted: Thu Jun 19, 2003 4:51 am
by angga888
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!
Posted: Wed Sep 24, 2003 7:35 am
by babor
Reda the new problem description.
315 : Network - How to get a better timing?
Posted: Mon Jan 26, 2004 3:17 am
by junbin
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?
Posted: Mon Jan 26, 2004 6:59 am
by titid_gede
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.
small problem 315
Posted: Tue Jul 06, 2004 5:15 pm
by Opexoc
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++ ?
Posted: Mon Nov 01, 2004 1:26 am
by david
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]
Posted: Mon Nov 01, 2004 10:15 am
by Raiyan Kamal
how about this :
the output should be
one more case:
output:
(nothing, program is supposed to terminate)
Posted: Mon Nov 01, 2004 5:08 pm
by david
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?
Posted: Sun Aug 07, 2005 6:14 am
by roticv
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];
}adj;
adj list[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*/
addvertex(p,q);
addvertex(q,p);
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;
}
315 - Network
Posted: Sat Sep 24, 2005 12:33 pm
by Faisal_Bd
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?
Posted: Mon Sep 26, 2005 6:50 am
by CodeMaker
Hi, I am also getting WA for this problem, this is my first articulation point code...... so I am a bit confused, is my code wrong or there is some special cases that I have to take care. plz help me on that. thanks.