Pagini recente » Cod sursa (job #2666857) | Cod sursa (job #2372732) | Cod sursa (job #416442) | Cod sursa (job #1380287) | Cod sursa (job #1704423)
//package problemetest2;
import java.io.*;
import java.util.*;
class Main {
static ArrayList<ArrayList<Integer>> graf = new ArrayList<ArrayList<Integer>>();
static int[] idx, lowlink, c;
static int index;
static int nr;
static Stack s = new Stack();
static public void CTC_Tarjan(){
index = 0;
for(int i = 1; i < idx.length; i ++)
if(idx[i] == 0)
Tarjan(i);
return ;
}
static public int Tarjan(int v){
idx[v] = index;
lowlink[v] = index;
index ++;
s.push(v);
int x;
for(int u : graf.get(v)){
if(idx[u] == 0){
Tarjan(u);
lowlink[v] = Math.min(lowlink[v], idx[u]);
}else{
if(s.contains(u)){
lowlink[v] = Math.min(lowlink[v], idx[u]);
}
}
}
if(lowlink[v] == idx[v])
nr++;
do{
x = (int) s.pop();
}while (x != v);
return v;
}
public static void main(String[] args) throws IOException {
BufferedReader in = null;
BufferedWriter out = null;
in = new BufferedReader(new FileReader("dfs.in"));
out = new BufferedWriter(new FileWriter("dfs.out"));
String[] line = in.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
int n1, n2;
idx = new int[n + 1];
lowlink = new int[n + 1];
c = new int[n + 1];
for (int i = 0; i < n + 1; i++)
graf.add(i, new ArrayList<Integer>());
for (int i = 0; i < m; i++) {
line = in.readLine().split(" ");
n1 = Integer.parseInt(line[0]);
n2 = Integer.parseInt(line[1]);
graf.get(Integer.parseInt(line[0])).add(Integer.parseInt(line[1]));
graf.get(Integer.parseInt(line[1])).add(Integer.parseInt(line[0]));
}
CTC_Tarjan();
out.write(String.valueOf(nr));
in.close();
out.close();
}
}