ELMaestro's blog

By ELMaestro, 10 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://mirror.codeforces.com/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;
	}
	
}

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

| Write comment?
»
10 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

graph.get(x).add(y);

graph.get(y).add(x);

The graph is directional, so you need to do only graph.get(x).add(y);

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In addition to what vintage_Vlad_Makeev wrote,

  • Your code never outputs 1 or n.
  • Addition can overflow.
  • It seems that your code counts the number of paths from each vertex i to vertex t. If so, this works only if this number is finite, but this is not necessarily the case; think what happens if the input graph contains a directed cycle. I am afraid that you have to reconsider the algorithm.
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the reply ,, I changed the code to output 1 but I don't want to output n in any case ,this made it get TLE in case 36 ,but I think the code works with a graph that contains a cycle because I used an array visited which continue looking for other unvisited nodes if the node is visited and I tried this case and it worked :- 4 4 1 4 1 2 2 3 3 4 3 1 Specifically ,what I want to reach is to get these nodes which will be surely present in any path from s to t , so I counted all the paths from s to t and while doing that I knew how many times every node is present in these paths and I output those nodes which are present in every path .The Question is how to optimize my code to reach this or which algorithm I should think of ? Thanks

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 5   Vote: I like it +3 Vote: I do not like it

      I don't understand your code very well, so I'm unable to point exactly what's wrong with it.

      However, what you're looking for are articulation points (if the king must pass in a city no matter what, it means that removing that city would disconnect the graph). Do some search on algorithms to find articulation points, it might help.

      I think what you need to do is something like: find articulation points, for each one found check if it disconnects s from t.