import java.io.*;
import java.util.*;
import java.math.*;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(
				System.out));
		String[] temp = in.readLine().split(" ");
		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]);
		SCC scc = new SCC(n);
		for(int i = 0; i < m; i++){
			StringTokenizer st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			scc.link[a].add(b);
			scc.conlink[b].add(a);
		}
		int res = scc.genDAG();
		if(res >= 0){
			out.write(scc.val[res] + "\n");
		}
		else{
			out.write("0\n");
		}
		out.flush();
	}
}
class SCC{
	public int[] f, par, val, in;
	public boolean[] vis;
	public LinkedList<Integer>[] link, conlink;
	public int index, n, ans;
	public boolean[][] map;
	
	public SCC(int a){
		n = a;
		f = new int[n];
		par = new int[n];
		vis = new boolean[n];
		link = new LinkedList[n];
		conlink = new LinkedList[n];
		for(int i = 0; i < n; i++){
			link[i] = new LinkedList<Integer>();
			conlink[i] = new LinkedList<Integer>();
		}
		index = 0;
		ans = 0;
	}
	
	public void dfs(int cur){
		vis[cur] = true;
		for(int i = 0; i < link[cur].size(); i++){
			Integer t = (Integer)link[cur].get(i);
			if(!vis[t]){
				dfs(t);
			}
		}
		f[this.index++] = cur;
	}
	public void condfs(int cur){
		vis[cur] = true;
		par[cur] = this.ans;
		for(int i = 0; i < conlink[cur].size(); i++){
			Integer t = (Integer)conlink[cur].get(i);
			if(!vis[t]){
				condfs(t);
			}
		}
	}
	public int genDAG(){
		Arrays.fill(vis, false);
		for(int i = 0; i < n; i++){
			if(!vis[i])
				dfs(i);
		}
		Arrays.fill(vis, false);
		for(int i = n - 1; i >= 0; i--){
			if(!vis[f[i]]){
				condfs(f[i]);
				this.ans++;
			}
		}
		in = new int[this.ans];
		val = new int[this.ans];
		for(int i = 0; i < n; i++){
			val[par[i]]++;
			for(int j = 0; j < conlink[i].size(); j++){
				int t = (Integer)conlink[i].get(j);
				if(par[i] == par[t])
					continue;
				in[par[t]]++;
			}
		}
		int count = 0;
		int which = -1;
		for(int i = 0; i < this.ans; i++){
			if(in[i] == 0){
				count++;
				which = i;
			}
		}
		if(count == 1)
			return which;
		return -1;
	}
}

• Re:总是RE，追了好久也不知道哪里出了问题，各位大虾帮我看看好吗？ (22) Iambitious 2007-03-21 14:36:51