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

Post by epsilon0 » Tue Nov 12, 2002 11:19 pm

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

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

315: Network

Post by kmhasan » Tue Nov 26, 2002 8:02 pm

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?

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Tue Nov 26, 2002 9:02 pm

Ignore the previous post. :oops:
I got AC. :P
The output for the test file I had, itself was wrong. :evil:

davidsu
New poster
Posts: 3
Joined: Fri Jan 31, 2003 10:02 am

Post by davidsu » Fri Jan 31, 2003 10:07 am

I got WA too,I got 8 with kmhasan's test case,could anyone give me more test case?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Thu Jun 19, 2003 4:51 am

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

User avatar
babor
New poster
Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm
Contact:

Post by babor » Wed Sep 24, 2003 7:35 am

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?

Post by junbin » Mon Jan 26, 2004 3:17 am

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

Post by titid_gede » Mon Jan 26, 2004 6:59 am

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

Post by Opexoc » Tue Jul 06, 2004 5:15 pm

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

Post by david » Mon Nov 01, 2004 1:26 am

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
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Mon Nov 01, 2004 10:15 am

how about this :

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

Post by david » Mon Nov 01, 2004 5:08 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

Post by roticv » Sun Aug 07, 2005 6:14 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];
}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;
}

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

315 - Network

Post by Faisal_Bd » Sat Sep 24, 2005 12:33 pm

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?

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 6:50 am

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.

Code: Select all

Accepted
Last edited by CodeMaker on Mon Sep 26, 2005 7:41 pm, edited 1 time in total.
Jalal : AIUB SPARKS

Post Reply

Return to “Volume 3 (300-399)”