|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 1e5 + 10, M = N << 1;
|
|
|
|
|
|
int n, m;
|
|
|
int in[N]; // 入度数组
|
|
|
bool flag[N]; // 用于判断所在连通分量是否是目标连通分量，是则为1
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 有向图求强连通分量
|
|
|
int stk[N], top; // tarjan算法需要用到的堆栈
|
|
|
bool in_stk[N]; // 是否在栈内
|
|
|
int dfn[N]; // dfs遍历到u的时间
|
|
|
int low[N]; // 从u开始走所能遍历到的最小时间戳
|
|
|
int ts; // 时间戳,dfs序的标识,记录谁先谁后
|
|
|
int id[N], scc_cnt; // 强连通分量块的最新索引号
|
|
|
int sz[N]; // sz[i]表示编号为i的强连通分量中原来点的个数
|
|
|
// tarjan算法求强连通分量
|
|
|
void tarjan(int u) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
in_stk[u] = 1;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else if (in_stk[v])
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++scc_cnt; // 强连通分量的序号
|
|
|
int x; // 临时变量x,用于枚举栈中当前强连通分量中每个节点
|
|
|
do {
|
|
|
x = stk[top--]; // 弹出节点
|
|
|
in_stk[x] = false; // 标识不在栈中了
|
|
|
id[x] = scc_cnt; // 记录每个节点在哪个强连通分量中
|
|
|
sz[scc_cnt]++; // 这个强连通分量中节点的个数+1
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
while (m--) {
|
|
|
int a, b;
|
|
|
scanf("%d %d", &a, &b);
|
|
|
add(a, b); // 有向图
|
|
|
}
|
|
|
// Tarjan算法套路
|
|
|
for (int i = 1; i <= n; i++) // 疑问：如果有多个彼此不连通的连通块，那是不是不存在可以到达所有点的点集？
|
|
|
if (!dfn[i]) tarjan(i);
|
|
|
|
|
|
// 枚举所有出边
|
|
|
for (int u = 1; u <= n; u++)
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
int a = id[u], b = id[v]; // u和v不属于同一个强连通分量,且是u ->v
|
|
|
if (a != b) in[b]++; // 则v所在的强连通分量的入度+1
|
|
|
}
|
|
|
|
|
|
// 遍历每个强连通分量，找出入度为0的强连通分量
|
|
|
for (int i = 1; i <= scc_cnt; i++)
|
|
|
if (!in[i]) flag[i] = 1;
|
|
|
|
|
|
// 遍历每个节点，如果它所在有强连通分量是入度为零的，则把此点记录到答案数组中,
|
|
|
// 并且，修改此强连通分量的入度不是0，防止再次被加入到答案数组中
|
|
|
set<int> ans;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int x = id[i];
|
|
|
if (flag[x]) {
|
|
|
ans.insert(i);
|
|
|
flag[x] = 0;
|
|
|
}
|
|
|
}
|
|
|
cout << ans.size() << endl;
|
|
|
for (auto x : ans) cout << x << " ";
|
|
|
return 0;
|
|
|
} |
