ELMaestro's blog

By ELMaestro, 11 years ago, In English

Can somebody help me finding a case in which this solution won't work ,I submitted it but it goes worng in case 4 ? It is problem A in this contest

[problem:http://codeforces.net/gym/100016 ]

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class Berland {

	/**
	 * @param args
	 */
	static ArrayList<ArrayList<Integer>>graph;
	static boolean []visited;
	static int count;
	static int[]cnt;
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc=new Scanner(new File("assassination.in"));
		
	   int n=sc.nextInt();
	   int m=sc.nextInt();
	   int s=sc.nextInt();
	   int t=sc.nextInt();
	   graph=new ArrayList<ArrayList<Integer>>();
	   visited=new boolean[n+1];
	   cnt=new int[n+1];
	   for(int i=0;i<=n;i++){
		   graph.add(new ArrayList<Integer>());
	   }
	   
		for(int i=0;i<m;i++){
			int x=sc.nextInt();
			int y=sc.nextInt();
			
			graph.get(x).add(y);
			graph.get(y).add(x);
			
		}
		
	     dfs(s,t);
	     int rslt=0;
		for(int i=2;i<cnt.length;i++){
			if(cnt[i]==count){
				rslt++;
			}
		}
		System.out.println(rslt);
		for(int i=2;i<cnt.length;i++){
			if(cnt[i]==count){
				System.out.print(i+" ");
			}
		}
		//System.out.println(Arrays.toString(cnt));
//System.out.println(count);
	}
	private static int dfs(int s, int t) {
		//System.out.println(s);
		
		if(s==t){
			//cnt[parent]++;
            count++;
			return 1;
		}
		
		//cnt[s]++;
		visited[s]=true;
		int cntt=0;
		int sum=0;
		for(Integer E:graph.get(s)){
			
			if(visited[E]){
				continue;
			}
			else {
				cntt=dfs(E,t);
				cnt[s]+=cntt;
				sum+=cntt;
				visited[E]=false;
			}
			
		}
	
		return sum;
	}
	
}

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it