Moderator: Board moderators

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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

``````
These test cases don't exist and are incorrect.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

You could easily write a brute force solution to check your answers. IE, if you remove an edge, are there more connected components?

In fact, even a brute force solution will get you AC within the time limit... for now I guess.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Your output assumptions are correct. X is always less than Y.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

796 ,WA = wrong articulation , helppp.

Hey. I got WA but I used almost the same code for Articulation point and got acc.Anybody here or all sleeping? Help me please.
..........................................................................................................
#include <stdio.h>
struct a
{
int d,c,data,p,l,f;

}g[1005][1005];

int edge[1000][2],ei,v,time;
void visit(int u){
int i;
g.c=1;
++time;
g.l=time;
g.d=time;
for(i=0;i<v;i++)
{

if(g.data==1 && g.c==0 && i!=g.p)
{
g.p=u;
visit(i);
if(g.l<g[u].l)
g[u][u].l =g.l;
if(g[i].l>g[u][u].d)
{
if(i<u)
{
edge[ei][0]=i;
edge[ei][1]=u;
ei++;
}
else
{
edge[ei][0]=u;
edge[ei][1]=i;
ei++;
}
}//if

}//if

else if(g[u][i].data==1 && i!=g[u][u].p && g[i][i].d<g[u][u].d && g[i][i].d<g[u][u].l )
{
g[u][u].l=g[i][i].d;

}

}
g[u][u].c=2;
time++;
g[u][u].f=time;

}

void dfs(){
int i;
for(i=0;i<v;i++)
{
g[i][i].c=0;
g[i][i].p=-1;
}
ei=0;
time=0;
for(i=0;i<v;i++)
{
if(g[i][i].c==0)
visit(i);
}

}

void main()
{

long int n,i,j,k,x,y,nx;
int temp;
char c;

while(scanf("%ld",&n)==1 ){
v=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g[i][j].data=0;
for(i=0;i<n;i++){

scanf("%ld",&x);
while(getc(stdin)!='(');
scanf("%ld",&nx);
while(getc(stdin)!=')');
while(nx-->0)
{
scanf("%ld",&y);
g[x][y].data=1;
g[y][x].data=1;
}

}

dfs();

for(i=0;i<ei-1;i++)
for(j=i+1;j<ei;j++)
{
if(edge[i][0]>edge[j][0])
{
temp = edge[i][0];
edge[i][0]=edge[j][0];
edge[j][0]=temp;

temp = edge[i][1];
edge[i][1]=edge[j][1];
edge[j][1]=temp;

}

}//for
for(i=0;i<ei;i++)
{
printf("%d - %d\n",edge[i][0],edge[i][1]);
}
printf("\n");
}

}
Life is a challenge.

cycos83
New poster
Posts: 2
Joined: Wed Jan 18, 2006 10:42 am

796 help me... Wa... Wa... Wa....

#include <stdio.h>
#include <algorithm>

using namespace std;

int map[1001][1001], n, check[1001], sum, save[1001][1001], num[1001];

void DFS(int p, int end)
{
int i;
if(p == end)
{
sum++;
return;
}
check[p]=1;
for(i=1;i<=map[p][0];i++)
{
if(check[map[p]]==0 && map[p]!=p)
{
DFS(map[p], end);
}
}
check[p]=0;
return;
}

int main()
{
int i, j, k, s, e, m, total;
while(1)
{
total=0;
scanf("%d",&n);
if(n==0)
{
break;
}
for(i=0;i<n;i++)
{
check=0;
num=0;
}
for(i=0;i<n;i++)
{
scanf("%d (%d)",&s,&m);
num=s;
map[s][0]=m;
for(j=1;j<=m;j++)
{
scanf(" %d",&e);
map[s][j]=e;
}
}
sort(num, num+n);
for(i=0;i<n;i++)
{
save[num][0]=0;
for(j=1;j<=map[num][0];j++)
{
sum = 0;
if(num < map[num][j])
DFS(num[i], map[num[i]][j]);
if(sum == 1)
{
total++;
save[num[i]][0]++;
save[num[i]][save[num[i]][0]] = map[num[i]][j];
}
}
}
if(total != 0)
{
for(i=0;i<n;i++)
{
k = save[num[i]][0];
if(k!=0)
{
sort(save[num[i]]+1,save[num[i]]+1+k);
for(j=1;j<=k;j++)
{
printf("%d - %d\n",num[i],save[num[i]][j]);
}
}
}
}
printf("\n");
}
return 0;
}

--------------------------------------------

give me data

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm
Maybe this input is useful for those geting WA:

Code: Select all

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

20
0 (1) 1
1 (4) 0 2 4 5
2 (4) 1 5 6 10
3 (1) 4
4 (4) 1 3 5 8
5 (6) 1 2 4 8 9 10
6 (3) 2 10 13
7 (1) 8
8 (4) 4 5 7 9
9 (3) 5 8 10
10 (4) 2 5 9 6
11 (3) 12 13 17
12 (3) 11 14 15
13 (5) 6 11 14 17 18
14 (4) 12 13 15 18
15 (4) 12 14 16 18
16 (1) 15
17 (3) 11 13 19
18 (3) 13 14 15
19 (1) 17

19
0 (2) 1 2
1 (2) 0 3
2 (2) 0 3
3 (3) 1 2 4
4 (6) 5 6 3 10 7 8
5 (2) 4 6
6 (2) 5 4
7 (3) 9 8 4
8 (2) 4 7
9 (1) 7
10 (3) 11 12 4
11 (2) 10 13
12 (2) 10 13
13 (3) 11 12 14
14 (3) 13 15 16
15 (2) 14 16
16 (4) 14 15 17 18
17 (2) 16 18
18 (2) 16 17

7
0 (3) 1 2 4
1 (3) 0 2 3
2 (3) 1 0 3
3 (4) 0 1 2 4
4 (3) 3 6 5
5 (1) 4
6 (1) 4
``````
And the AC output is

Code: Select all

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

0 - 1
3 - 4
6 - 13
7 - 8
15 - 16
17 - 19

3 - 4
4 - 10
7 - 9
13 - 14

3 - 4
4 - 5
4 - 6
``````

sethos
New poster
Posts: 2
Joined: Mon Nov 13, 2006 4:21 pm

Code: Select all

``got acc``

uva3
New poster
Posts: 1
Joined: Fri Dec 29, 2006 1:32 am

Code: Select all

``````2

import java.io.IOException;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

class Main {

int blok=1,server1,server2,critical,iVis;
int[][]data;
int[]critField,visited;
boolean jump;

public static void main(String[] args) {
Main m=new Main();
m.begin();
}

void print(){

System.out.println();

for(int i=0;i<critField.length;i++){

if(critField[i]!=-1){

int a=i,b=critField[i];

if(a>b){
int c=a;
a=b;
b=c;
}
System.out.println(a+" - "+b);
}
}
System.out.println();
}

boolean testVisit(int a){

for(int i=0;i<visited.length;i++ ){
if(visited[i]==-1)
break;
if(visited[i]==a){
return true;
}
}
return false;
}

void insertCrit(int a,int b){

if(a>b){
int c=a;
a=b;
b=c;
}
if((critField[a]==-1)){	     //empty
critField[a]=b;
critical++;
return;
}
if((critField[a]==b)||(critField[b]==a)){
return;

}
if(critField[a]>b){			// case 4-6 , 4-5
int c=critField[a];
critField[a]=b;
critField[c]=a;
critical++;
}else{
critField[b]=a;			// case 4-5 , 4-6
critical++;

}
}

public void bridge(int actual){

boolean visit;

for(int i=0;i<data[actual].length;i++){

if(jump)
return;

visit=testVisit(data[actual][i]);

if(((actual==server2)&&(data[actual][i]==server1))||
(data[actual][i]==-1)||(visit))
continue;

if((! visit)&&(data[actual][i]==server1)){
jump=true;
return ;

}else{
visited[iVis++]=data[actual][i];
bridge(data[actual][i]);
}
}
}

public void solve(){

setCrit();

for(int i=0;i<data.length;i++){

server1=i;

for(int j=0;j<data[i].length;j++){

setVisited();
iVis=0;

server2=data[server1][j];

if(data[server1].length==0){
continue;
}

if(data[server1].length==1){
insertCrit(server1,server2);
continue;
}

jump=false;

bridge(server2);

if(! jump){
insertCrit(server1,server2);
}
}
}
}

void setCrit(){
critical=0;
for(int i=0;i<critField.length;i++){
critField[i]=-1;
}
}
void setVisited(){
visited=new int[critField.length];
for(int i=0;i<visited.length;i++){
visited[i]=-1;
}
}

void begin(){

String input;
StringTokenizer idata;

int a=0,b,c,count=0;

while ((input = Main.ReadLn (255)) != null) {

idata = new StringTokenizer (input);

switch(blok){

case 1:
try{
a = Integer.parseInt (idata.nextToken());
}catch(NoSuchElementException nsee){
continue;
}

if(a==0){
count=-1;
break;
}
data=new int[a][];

count=0;

blok=2;
break;

case 2:
b = Integer.parseInt (idata.nextToken());

c = Integer.parseInt (idata.nextToken());

if((a==1)&&(c==0)){
blok=1;
count=-1;
break;
}

count++;

data[b]=new int[c];
critField=new int[a];

if(c==0){

break;
}

for(int i=0;i<data[b].length;i++){

data[b][i]=Integer.parseInt (idata.nextToken());
}
break;
}
if(count==a){

solve();
print();
blok=1;
}
}
}
/******************************************************/

static String ReadLn (int maxLg)   {

byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

try  {

while (lg < maxLg) {

if ((car == '(')|| (car == ')'))
continue;

if ((car<0)||(car == '\n'))
break;
lin [lg++] += car;
}
}
catch (IOException e) {
return (null);
}

if ((car < 0) && (lg == 0))
return (null);  // eof

return (new String (lin, 0, lg));
}
}

``````

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:

WA

Code: Select all

``````ACC..

:)

``````
I don't understand why WA!!! plz help
form kisui na ... class tai asol....
iF U hv d class u get the form....

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Code: Select all

``````7
0 (3) 1 2 4
1 (3) 0 2 3
2 (3) 1 0 3
3 (4) 0 1 2 4
4 (3) 3 6 5
5 (1) 4
6 (1) 4``````
Is this input correct? Vertex 3 has connection to 0 but 0 doesn't have connection to 3. Same with 0 and 3. Links are bidirectional, so i supposed that the link would appear on the adjacency list of both vertices.

Code: Select all

``````3 critical links
3 - 4
4 - 5
4 - 6``````
I think that this output isn't correct. Edge between 3 - 4 is not a bridge. Funny that my algorithm based on finding the articulation points in O( V + E ) gives the same. But my brute force solution doesn't.

What i don't understand is that both solutions gave Wrong Answer

Here is my brute force:

Code: Select all

``````got ACC. Missed a newline always after a test case
``````
Are there other problems about bridges ?
Miguel Oliveira

Ratul Ahmed
New poster
Posts: 4
Joined: Mon Aug 30, 2010 3:40 am

still im getting WA.
why???????
pls help me!!!!!

here is my algo...
first i find tree edge.
then i marked a vertex with back edge vertex's dfn.
if a vertex or its ancestor has back edge then it has no critical link

here is my code....

Code: Select all

``````#include<cstdio>  //WA
#include<vector>
#include<stack>
using namespace std;

#define MAX 1005

bool a[MAX][MAX];
bool flag[MAX];

class DFS
{
long N,root;
vector<long> V,low;
/*index of V or value of low is dfn(DFS Number or order)*/

public:

vector<long> AP1,AP2;  /*AP1,AP2=Articulation Point. AP1 contians lower number*/

bool sort_store(long X,long Y)
{
long I,key1,key2;
/*sort first articulation point*/
if( X<Y )
{
AP1.push_back( X );
AP2.push_back( Y );
}
else
{
AP1.push_back( Y );
AP2.push_back( X );
}
/*insertion sorting articulation points*/
I=AP1.size()-1;
key1=AP1[I];
key2=AP2[I];
/*sorting according to 1st articulation point*/
for(I--; AP1[I]>key1 && I>=0 ;I--)
{
AP1[I+1]=AP1[I];
AP2[I+1]=AP2[I];
}
/*sorting according to 2nd articulation point*/
for( ; AP2[I]>key2 && AP1[I]==key1 && I>=0 ;I--)
{
AP2[I+1]=AP2[I];
}
AP1[I+1]=key1;
AP2[I+1]=key2;

return 1;
}

/**** DFS_visit ****/
bool DFS_visit(long start)
{
long I,J,K,L,size;
stack<long> SJ;

V.push_back(start);
low.push_back(V.size()-1);
flag[V.back()]=1;
SJ.push(0);
while( V.size() )
{
I=V.back();
for(J=SJ.top(); J<N ;J++)
{
if( a[I][J] )
{
a[I][J]=0;
a[J][I]=0;
if( !flag[J] )
{
V.push_back(J);
low.push_back(V.size()-1);
flag[V.back()]=1;
SJ.top()=J+1;
SJ.push(0);
break;
}
else
{
for(K=0; V[K]!=J ;K++);
if( low.back()>K )
low.back()=K;
}
}
}
if( J<N )
continue;
size=V.size();
if( size>1 )
{
if( low.back()>=V.size()-1 && V.back()!=root )
{
sort_store(V[size-1],V[size-2]);
}
else if( low[size-2]>low[size-1] )
{
low[size-2]=low[size-1];
}
}
V.pop_back();
low.pop_back();
}

return 1;
}
/**** DFS ****/
DFS(long node)
{
long I,J;
N=node;
for(I=0;I<N;I++)
{
if( !flag[I] )
{
V.clear();
low.clear();
root=I;
DFS_visit(I);
//for(I=0;I<V.size();I++)
//  printf("%ld -> %ld_%ld\n",V[I],I,low[I]);
}
}

}
};

class INPUT
{
long N,I,J,K,H,S,C;

bool print(long N)
{
long I,J;
for(I=0;I<N;I++)
{
for(J=0;J<N;J++)
printf(" %d",a[I][J]);
printf("\n");
}
return 1;
}

public:

INPUT()
{
for(I=0;I<MAX;I++)
for(J=0;J<MAX;J++)
a[I][J]=0;

while( scanf("%ld",&N)==1 )
{
for(I=0;I<N;I++)
flag[I]=0;

for(K=0; K<N ;K++)
{
scanf("%ld",&S);
while( getchar()!='(' );
scanf("%ld",&C);
getchar();

if( !C )
flag[S]=1;  /*ignoring the vertex which has no adjcent*/
else
for(J=0; J<C ;J++)
{
scanf("%ld",&H);
a[S][H]=1;
a[H][S]=1;
}
}
//print(N);
DFS B(N);
//print(N);
for(I=0;I<B.AP1.size();I++)
printf("%ld - %ld\n",B.AP1[I],B.AP2[I]);
printf("\n");
}
}
};

int main()
{
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
INPUT A;

return 0;
}
``````

shtorm941
New poster
Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm

I used standart algo for searching bridges, but got a WA.

http://ideone.com/qbu9F

Code: Select all

``````import java.io.*;
import java.util.*;

public class Main {
static int n;
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
static int[][] a;
static int[][] ans;
static int ansCount;

static boolean[] used;
static int timer;
static int[] tin;
static int[] tup;

static void read() throws IOException {
n = sc.nextInt();
a = new int[n][];
ansCount = 0;
ans = new int[n][2];
for(int l = 0; l < n; l++) {
int i = sc.nextInt();
String s = sc.next();
int count = Integer.parseInt(s.substring(1, s.length() - 1));
a[i] = new int[count];
for(int k = 0; k < count; k++)
a[i][k] = sc.nextInt();
}

}

static void out() {
Arrays.sort(ans, 0, ansCount , new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if(o1[0] > o2[0])
return 1;
else
if(o1[0] < o2[0])
return -1;
if(o1[1] > o2[1])
return 1;
else
return -1;
}
});

for(int i = 0; i < ansCount; i++) {
pw.println(ans[i][0] + " - " + ans[i][1] );
}
}

static void bridge(int a, int b) {
ans[ansCount][0] = Math.min(a, b);
ans[ansCount][1] = Math.max(a, b);
ansCount++;
}

static void solve() {
timer = 0;
used = new boolean[n];
tin = new int[n];
tup = new int[n];
for(int i = 0; i < n; i++)
if(!used[i])
dfs(i, -1);
}

static void dfs(int v, int p) {
used[v] = true;
tin[v] = tup[v] = timer++;
for(int i = 0; i < a[v].length; i++) {
int to = a[v][i];
if(to == p)
continue;
if(used[to])
tup[v] = Math.min(tup[v], tin[to]);
else {
dfs(to, v);
tup[v] = Math.min(tup[v], tup[to]);
if(tin[v] < tup[to])
bridge(v, to);
}

}

}

public static void main(String[] args) throws IOException {
try
{
while(true) {
solve();
out();
if(sc.hasNext())
pw.println();
else
return;
}

}
finally {
pw.close();
}

}

}
``````

ducse1527
New poster
Posts: 1
Joined: Tue Jun 19, 2012 9:01 am

Check whether you have done two things:
1. Print a blank line after every test cases.
2. first element of two links are similar then sort them ascending orderly to their second element.

shtorm941
New poster
Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm

ducse1527 wrote:Check whether you have done two things:
1. Print a blank line after every test cases.
2. first element of two links are similar then sort them ascending orderly to their second element.
1. I print a blank line. Look at this: http://ideone.com/qbu9F
2.Also I sort edges by first element and then (if first elements are equals) sort by second element.

Code: Select all

``````new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if(o1[0] > o2[0])
return 1;
else
if(o1[0] < o2[0])
return -1;
if(o1[1] > o2[1])
return 1;
else
return -1;
}
})``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA