796 - Critical Links
Posted: Thu Mar 18, 2004 5:54 pm
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]
