796 - Critical Links

[daveon]

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

These test cases don't exist and are incorrect.

[daveon]

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]

Your output assumptions are correct. X is always less than Y.

[Shuvra(CSE-BUET)]

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
printf("%d critical links\n",ei);
for(i=0;i<ei;i++)
{
printf("%d - %d\n",edge[i][0],edge[i][1]);
}
printf("\n");
}

}

[cycos83]

#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)
{
printf("0 critical links");
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];
}
}
}
printf("%d critical links\n",total);
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]

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

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

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

3 critical links
3 - 4
4 - 5
4 - 6

[sethos]

Code: Select all

got acc

[uva3]

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();
		
		System.out.println(critical+" critical links");
		
		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){
        		  System.out.println(0+" critical links\n");
        		  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)){
					System.out.println(0+" critical links\n");
					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) {
            	
                car = System.in.read();
                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]

Code: Select all

ACC..

:)

I don't understand why WA!!! plz help

[mogers]

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 ?

[Ratul Ahmed]

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
else it has 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);
                printf("%ld critical links\n",B.AP1.size());
                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]

Please, help me with it.
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 BufferedReader br;
	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() {
		pw.println(ansCount + " critical links");
		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) {
				read();
				solve();
				out();
				if(sc.hasNext())
					pw.println();
				else
					return;
			}
			
		}
        finally {
        	pw.close();
        }
            
    }
            
}

[ducse1527]

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]

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]

1. Print a blank line after every test cases - including the last one.