Moderator: Board moderators

This is my solutiuon. It gets WA, but I'm sure it's right.
I think i didn't clearly understood the way in which critical links should be printed.
My suggestion: for example, program found a critical link x - y.
I put all those links in array rs and then sort it with default qsort routine, but... WA
Then I suggested this:
If x > y then x and y must be swapped, so on the first place it's always the minimal server no. And it's still WA.

Can somebody help me by giving advice of output format or some critical tests?
Thanx
[cpp]
#include <fstream.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#ifndef ONLINE_JUDGE

#include <conio.h>
const long MAX = 1000;

#else

const long MAX = 10000; // maximium number of servers. I suppoes it's enough

#endif

long finish = 0;
long N, res = 0;
long ord[MAX], low[MAX];
long cnt = 0;
struct RS{
long x, y;
} rs[MAX];

struct List{
long v;
List *next;

List(){
v = -1;
next = NULL;
}
} *list[MAX];

long find(long a, long b){
List *l = list[a];

while (l){
if (l->v == b)
return 1;
l = l->next;
}

return 0;
}

List *l = list[a];

if (find(a, b))
return;
while (l->next)
l = l->next;
List *r = new List;
r->v = b;
l->next = r;
}

void clear(List *l){
List *r;

while (l){
r = l->next;
delete l;
l = r;
}
}

void Input() {
long sc, i, j, k;
char c;

res = cnt = 0;

cin >> N;
if (finish = cin.eof())
return;

memset(low, 0, sizeof low);
memset(rs, 0, sizeof rs);

for (k = 0; k < N; k++){
clear(list[k]);
list[k] = new List;
ord[k] = -1;
}
for (long n = 0; n < N; n++){
cin >> i;

cin >> c;
cin >> sc;
cin >> c;
for (k = 0; k < sc; k++){
cin >> j;
}
}
}

void DFS(long v, long w){
List *l;
long i;

ord[v] = cnt++;
low[v] = ord[v];

l = list[v];
while (l = l->next){
i = l->v;
if (ord[i] == -1){
DFS(i, v);
if (low[v] > low[i])
low[v] = low[i];
if (low[i] == ord[i]){
rs[res].x = ((v > i) ? i : v);
rs[res].y = ((v < i) ? i : v);
res++;
}
} else
if (i != w)
if (low[v] > ord[i])
low[v] = ord[i];
}
}

void Solve() {
for (long i = 0; i < N; i++)
if (ord[i] == -1)
DFS(i, i);
}

int fcmp(const void *a, const void *b){
RS m = *(RS*)a;
RS n = *(RS*)b;

if (m.x > n.x)
return 1;
if (m.x < n.x)
return -1;

return 0;
}

void Output() {
qsort((void *)rs, res, sizeof rs[0], fcmp);
cout << res << " critical links" << endl;
for (long i = 0; i < res; i++)
cout << rs[i].x << " - " << rs[i].y << endl;
}

#define DEBUG

int main() {
#ifndef ONLINE_JUDGE
ifstream is("input.txt");
cin = is;
#ifdef DEBUG
clrscr();
#else
ofstream os("output.txt");
cout = os;
#endif
#endif
for (long i = 0; !finish; i++){
Input();
if (finish)
break;
Solve();
if (i)
cout << endl;
Output();
}
return 0;
}
[/cpp]
Who am I? Just eXon...
eXon
New poster

Posts: 17
Joined: Sun Mar 23, 2003 2:04 pm
Location: Russia

### 796 - Critical links - WA and WA

Could anyone post some IO, or help me and tell what's wrong ? I try to solve this problem using algorithm below, but without success ...

Explanation of variables:
color,p,d,L => arrays of size N
N => number of vertices in graph
[c]
spoiler removed[/c]
After running this routine, all brifges are marked by digit 2. So edge (u,v) is bridge if graph[u][v] == 2.

And one more question: we always outputs "X critical links" ? even if X == 1 ?

Best regards
DM
Last edited by Dominik Michniewski on Mon Sep 27, 2004 3:46 pm, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

Try with this.
input
Code: Select all
`20 (1) 11 (0) 010 (1) 1`

Output
Code: Select all
`1 critical links1 - 00 critical links`
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

one more think.
should it be like :
if(L[v] > d[u])
{
if(v > u) bridges++;
graph[u][v] = 2;

}
or,

if(L[v] > d[u])
{
if(v > u)
{
bridges++;
graph[u][v] = 2;
}

}
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

In first case my program outputs:

0 - 1

(bacause of this, that in this problem graph has bidirectional links ... and accroding to my output procedure - I listed only edges (u,v), in which u > v), but second case (in this problem), I think, is incorrect according to problem description. I still can't get Accepted this problem ... and any help is very good

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

I agree with you.Its annoying but sometimes we need to make a solution for some wrong cases.
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

I finally managed to get accepted this problem.
My error was :
if(u < v) bridges++;
graph[u][v] = graph[v][u] = 2; // <<-- here

If graph is bidirectional, and if edge (u,v) is bridge, that's true that edge (v,u) is edge too... I miss this one thing

Best regards
DM

PS. Thanks alu_mathics for hint with test cases ... Because of that I got a best time for this problem hehehehe
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

Wow you got the 1st place.Good job done.Congrates....
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

Yes, that nice very nice - I think that is first problem in which I have first place - and I think not last

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 796

I have tried this problem but go WA. Can anybody please help me with some critical input and output?
Faisal_Bd
New poster

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

Ops! got AC! It was again a silly mistake - initialization! initialized some variables and problem solved..
Faisal_Bd
New poster

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

Hi, i'm trying to solve this one but i'm geting a feel that the input isn't correct all the time.
alu_mathics wrote:Try with this.
input
Code: Select all
`20 (1) 11 (0) 010 (1) 1`

Output
Code: Select all
`1 critical links1 - 00 critical links`

How can this be correct input?!?!?

How to pass this one i did about dozens of tests, and it worked all the time, but on the grading i get "Wrong answer".
Is there something i should know.

Thanks.
NrmMyth
New poster

Posts: 3
Joined: Mon Mar 20, 2006 10:46 pm

### 796

I can't solve 796. My program handles the test input just fine, and it's handled every test I've come up with for it, but I still got WA...

Does anybody have some more test I/O for 796 that I could try my program on?

My algorithm is pretty simple (I'm using an adjacency matrix to store the undirected graph). If a vertex has no edges, then ignore it. If it has one edge, that edge is automatically a critical link. If the vertex has more than one edge, I (a) count how many nodes are indirectly connected to the current vertex, (b) disable a link, and (c) count again. If the count goes down, I tag that link a critical link.

(I was afraid the counting would be inefficient, but the time taken by the Judge was very low.)

As I said, it works for the sample I/O and several cases I made up myself (and some I/O cases I've seen here on the forums). It handles them all.

Why the WA?
Itch86
New poster

Posts: 1
Joined: Wed Apr 19, 2006 2:14 am

this problem is killing me by giving wa....i solved similar bridge detection problem (610) without any difficulty...i would appreciate some help
my algo :
1) start with some unvisited vertex and find all bridges in that conncected component using depth first search
2) in bridge procedure(in my program) ,whenever i find some edge as bridge, i stored that edge in vector .
3) finally after calling bridge procedure over all connected components...i sorted the resultant vector and displayed

i am getting wa..i could not figure out what is missing..pls have a look at following code:
Code: Select all
`int bcnt,cnt,nvertex,g[LIMIT][LIMIT],low[LIMIT],pre[LIMIT];vector<pair<int,int> > res;void bridge(int w){   pre[w]=cnt++; low[w]=pre[w];   for(int v=0;v<nvertex;v++)       if(g[w][v]) {          g[v][w]=0;          if(pre[v]==-1) {               bridge(v);               if(low[w]>low[v]) low[w]=low[v];               if(low[v]==pre[v]) { bcnt++; res.push_back(make_pair(w,v)); }          }          else             if(low[w]>pre[v]) low[w]=pre[v];      }}void dfs(void){   bcnt=0;   cnt=1;   res.clear();   r(i,nvertex) if(pre[i]==-1) bridge(i);    sort(res.begin(),res.end());   printf("%d critical links\n",bcnt);   r(i,bcnt) printf("%d - %d\n",res[i].first,res[i].second);   printf("\n");}     in main procedure i initialiized graph with input edges...`
Genius is a 2% inspiration and 98% perspiration
m_thimma
New poster

Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india

To m_thimma,
simply use white path theorem
which is f[w]>=d[u], where d is decover no & f is finishing no.
Just simple DFS code.
Remember one thing is w & u may be the same vertex. so dont consider this thing to find minimum number of finishing time.
then easily you will get the result for how to find bridges/critical links.

u~~w~~v