796 - Critical Links
Moderator: Board moderators
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[0], 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]
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[0], 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...
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
Try with this.
input
Output
input
Code: Select all
2
0 (1) 1
1 (0) 0
1
0 (1) 1
Code: Select all
1 critical links
1 - 0
0 critical links
cuii e
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
-
- 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 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
Hi, i'm trying to solve this one but i'm geting a feel that the input isn't correct all the time.
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.
How can this be correct input?!?!?alu_mathics wrote:Try with this.
inputOutputCode: Select all
2 0 (1) 1 1 (0) 0 1 0 (1) 1
Code: Select all
1 critical links 1 - 0 0 critical links
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.
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?
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?
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:
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
-
- 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.
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.