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;
}
}
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);
In addition to what vintage_Vlad_Makeev wrote,
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
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.