题目的意思是求有向图中满足“自己可达的顶点都能到达自己”的顶点个数
显然，在一个强连通分量中，每个点都符合要求，但是 如果强连通分量中有某个点跟外面的某个点相连了，这个强连通分量就不符合要求了，很显然，外面的点是无法回到这个点上的，如果能回到这个点，就是强连通分量中的一员了，这是矛盾的。
那么结论就是，缩点后，求出度为0的强连通分量中的顶点。
tarjan写的
#include <iostream>
#include <map>
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#define MAXN 5005
#define MAXM 50005
#define INF 1000000000
using namespace std;
int n, m;
int scc;//强连通分量
int index;//每个节点的dfs访问次序编号
int dfn[MAXN];//标记结点i的dfs访问次序
int low[MAXN];//记录节点u或u的子树中的所有节点的最小标号
int fa[MAXN];//属于哪个分支
bool instack[MAXN];//是否在栈中
int in[MAXN], head[MAXN], e;
int out[MAXN];//出度
stack <int>s;
struct Edge
{int v, next;
}edge[MAXM];
void insert(int x, int y)
{edge[e].v = y;edge[e].next = head[x];head[x] = e++;
}
void tarjan(int u)
{dfn[u] = low[u] = ++index;s.push(u);instack[u] = true;for (int j = head[u]; j != -1; j = edge[j].next){int v = edge[j].v;if(dfn[v] == 0)//未曾访问过{tarjan(v);low[u] = min(low[u], low[v]);}else if(instack[v])low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){scc++;while(1){int tmp = s.top();s.pop();instack[tmp] = 0;fa[tmp] = scc;if(tmp == u) break;}}
}
void init()
{scc = index = 0;memset(dfn, 0, sizeof(dfn));memset(instack, 0, sizeof(instack));e = 0;memset(head, -1, sizeof(head));memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));}
void solve()
{for (int i = 1;i <= n; i++){if (!dfn[i])tarjan(i);}for (int i = 1;i <= n; i++){for(int j = head[i]; j != -1; j = edge[j].next){int u = fa[i];int v = fa[edge[j].v];if(u != v){out[u]++;in[v]++;}}}for(int i = 1; i <= n; i++)if(out[fa[i]] == 0) printf("%d ", i);printf("\n");
}int main()
{int x, y;while(scanf("%d", &n) != EOF && n){init();scanf("%d", &m);while(m--){scanf("%d%d", &x, &y);insert(x, y);}solve();}return 0;
}
用Kosaraju写的
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 5005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct Edge
{int v, next;
}edge[10 * MAXN], revedge[10 * MAXN];
int head[MAXN], revhead[MAXN], e, visited[MAXN];
int order[MAXN], cnt, id[MAXN], used[MAXN];
int uu[5 * MAXN], vv[5 * MAXN], out[MAXN], pos;
int n, m;
void init()
{e = 0;memset(head, -1, sizeof(head));memset(revhead, -1, sizeof(revhead));memset(out, 0 , sizeof(out));memset(used, 0, sizeof(used));
}
void insert(const int &x, const int &y)
{edge[e].v = y;edge[e].next = head[x];head[x] = e;revedge[e].v = x;revedge[e].next = revhead[y];revhead[y] = e;e++;
}
void readdata()
{for(int i = 0; i < m; i++){scanf("%d%d", &uu[i], &vv[i]);insert(uu[i], vv[i]);}
}
void dfs(int u)
{visited[u] = 1;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!visited[v])dfs(v);}order[cnt++] = u;
}
void dfs_rev(int u)
{visited[u] = 1;id[u] = cnt;for(int i = revhead[u]; i != -1; i = revedge[i].next){int v = revedge[i].v;if(!visited[v])dfs_rev(v);}
}
void Kosaraju()
{init();readdata();memset(visited, 0, sizeof(visited));cnt = 0;for(int i = 1; i <= n; i++){if(!visited[i])dfs(i);}memset(visited, 0, sizeof(visited));cnt = 0;for(int i = n - 1; i >= 0; i--){if(!visited[order[i]]){cnt++;dfs_rev(order[i]);}}for(int i = 0; i < m; i++){int u = id[uu[i]];int v = id[vv[i]];if(u != v) out[u]++;}for(int i = 1; i <= cnt; i++){if(out[i] == 0){used[i] = 1;}}
}
int main()
{while(scanf("%d", &n) != EOF && n){scanf("%d", &m);Kosaraju();int ans[MAXN];int ct = 0;for(int i = 1; i <= n; i++){int t = id[i];if(used[t] == 1)ans[ct++] = i;}if(ct == 0) printf("\n");else{for(int i = 0; i < ct - 1; i++)printf("%d ", ans[i]);printf("%d\n", ans[ct - 1]);}}return 0;
}