OJ Board

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

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

Code: Select all

got acc

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

Code: Select all

ACC..

:)

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

Code: Select all

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

Code: Select all

got ACC. Missed a newline always after a test case

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

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

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