## 796 - Critical Links

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

eXon
New poster
Posts: 17
Joined: Sun Mar 23, 2003 2:04 pm
Location: Russia
Contact:

### 796 - Critical Links

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

void add_edge(long a, long b){
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;
add_edge(i, j);
add_edge(j, i);
}
}
}

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 == -1){
DFS(i, v);
if (low[v] > low)
low[v] = low;
if (low == ord){
rs[res].x = ((v > i) ? i : v);
rs[res].y = ((v < i) ? i : v);
res++;
}
} else
if (i != w)
if (low[v] > ord)
low[v] = ord;
}
}

void Solve() {
for (long i = 0; i < N; i++)
if (ord == -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, fcmp);
cout << res << " critical links" << endl;
for (long i = 0; i < res; i++)
cout << rs.x << " - " << rs.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...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
Try with this.
input

Code: Select all

``````2
0 (1) 1
1 (0) 0

1
0 (1) 1
``````
Output

Code: Select all

``````1 critical links
1 - 0

0 critical links
``````
cuii e

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
one more think.
should it be like :
if(L[v] > d)
{
if(v > u) bridges++;
graph[v] = 2;

}
or,

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

}
cuii e

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
In first case my program outputs:

1 critical links
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)

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
I agree with you.Its annoying but sometimes we need to make a solution for some wrong cases.
cuii e

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I finally managed to get accepted this problem.
My error was :
if(u < v) bridges++;
graph[v] = graph[v] = 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)

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
Wow you got the 1st place.Good job done.Congrates.... cuii e

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

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

### 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
Location: Bangladesh
Ops! got AC! It was again a silly mistake - initialization! initialized some variables and problem solved.. NrmMyth
New poster
Posts: 3
Joined: Mon Mar 20, 2006 10:46 pm
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

``````2
0 (1) 1
1 (0) 0

1
0 (1) 1
``````
Output

Code: Select all

``````1 critical links
1 - 0

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

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

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

m_thimma
New poster
Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india
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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
To m_thimma,
simply use white path theorem
which is f[w]>=d, 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

your code is too complicated.