315 - Network

[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

[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?

[kmhasan]

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

[davidsu]

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

[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!

[babor]

Reda the new problem description.

[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?

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

[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++ ?

[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]

[Raiyan Kamal]

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]

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?

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

[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?

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

Code: Select all

Accepted