Tarjan大家族

发表于 分类于 阅读次数：

基本变量

  • dfn[u]：搜索时间戳（DFS 序）
  • low[u]：能回溯到的最早时间戳

low[u] 的更新：

  1. 初始化：low[u] = dfn[u]
  2. 树边 u → v（u = fa(v)）：回溯时更新，low[v] 已知
    low[u] = min(low[u], low[v])
  3. 非树边 (u, v) ∉ dfs_tree：
    low[u] = min(low[u], dfn[v])

以下内容注重算法和代码，基本概念定义请自行搜索了解。

割点

  • 判定法则：dfn[u] <= low[v]，其中 v 为搜索树上 u 的子节点。特别地，u = root 时，需子节点 v1, v2 均满足。
  • 证明：考虑包含 (u, v) 的环结构。若 u 为割点（环顶），则仅当 (x, v) 一定包含 (u, v)，即外点 x 到达 v 必须晚于到 u，u 为必经关卡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int> g[N];
//priority_queue<int,vector<int>,greater<int>> cv; 
bool cv[N]; 
int n,m,dfn[N],low[N],cnt/*,son*/,i,ans;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	int son=0;//debug1:应该定义为局部变量，防止tarjan(v)中son值被改变
	for(int v:g[u])
	{
		if(!dfn[v])//v未遍历
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);//需要low[v]，所以要先深搜v，再更新low[u] 
			if(low[v]>=dfn[u])//鉴定为割点 
			{
				son++;
				//u==i即u为根节点，那就要至少两个子节点是割点（son>1)才满足割点条件 
				if(u!=i||son>1) cv[u]=1;//cv.push(u); debug2:一个点可能会被判多次割点，队列里会有重点（虽然可以强行去重但太麻烦了） 
			}
		} 
		else low[u]=min(low[u],dfn[v]); //回溯，用非搜索树上边更新
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back({y});
		g[y].push_back({x});
	}
	for(i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++) 
	{
		if(cv[i]) ans++;
	}
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++) 
	{
		if(cv[i]) cout<<i<<' ';
	}
    //cout<<cv.size()<<'\n';
	//while(cv.size()) cout<<cv.top()<<' ',cv.pop();
 	return 0;
}

割边

P1656 炸铁路

  • 判定法则：dfn[u] < low[v]，其中 v 为搜索树上 u 的子节点（不能取等，否则如果有重边则割边之后仍连通）。
  • 虽然是按点深搜，但其实是在遍历边。故不能走反边。
  • 如何标记反边？
    1. 序号标记，使正反边的序号满足成对一一映射。用 x ^ 1 = y。则 (x, y) 为相邻的奇数和偶数，例如 (2, 3)：2 ^ 1 = 3，3 ^ 1 = 2。
    2. 标记父节点（无法处理重边）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=151,M=5*1e3+5;
struct Edge{
	int a,b;
};
vector<Edge> e;//注意存图方式 e存边
vector<int> g[N];//g存节点→对应边的序号
int tot,cnt,len;
int n,m,dfn[N],low[N];
Edge bridge[M];
bool cmp(Edge x,Edge y)
{
	if(x.a==y.a) return x.b<y.b;
	return x.a<y.a;
}
void tarjan(int u,int in_edge)
{
	dfn[u]=low[u]=++tot;
	for(int id:g[u])
	{
		int v=e[id].b;
		if(!dfn[v])
		{
			tarjan(v,id);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v])
			{
				bridge[++len]={min(u,v),max(u,v)};
			}
		}
        //如果回溯时不是反边
		else if(id!=(in_edge^1)) low[u]=min(low[u],dfn[v]);
		//debug1:优先级^较低，记得加括号
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		e.push_back({y,x}),g[y].push_back(e.size()-1);
		e.push_back({x,y}),g[x].push_back(e.size()-1);
	}
	tarjan(1,0);
	sort(bridge+1,bridge+1+len,cmp);
	for(int i=1;i<=len;i++)
	{
		cout<<bridge[i].a<<' '<<bridge[i].b<<'\n'; 
	}
 	return 0;
}

强连通分量（SCC）

由 OI WIKI,
在有向图 $G$ 中，如果两个顶点间至少存在一条路径，称两个顶点强连通（strongly connected）。如果有向图 $G$ 的每两个顶点都强连通，称 $G$ 是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量（strongly connected components）。

对于一个这样的 DFS 搜索树：

  1. 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
  2. 反祖边（back edge）：示意图中以红色边表示（即 $7 \rightarrow 1$），也被叫做回边，即指向祖先结点的边。
  3. 横叉边（cross edge）：示意图中以蓝色边表示（即 $9 \rightarrow 7$），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先。
  4. 前向边（forward edge）：示意图中以绿色边表示（即 $3 \rightarrow 6$），它是在搜索的时候遇到子树中的结点的时候形成的。

反祖边（横叉边可能）$\to$ 环 $\to$ SCC。

所以对于一个 SCC，肯定含至少一个环，取环顶编号 $u$ 为特征值。（low[u] = dfn[u]，因为环内最小编号，low 值不更新）

在搜索树上表现为：如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。比如上图 $1 \rightarrow 2 \rightarrow 7 \rightarrow 1$ 的根就是 $1$，且 low[1,2,7] = 1。

  • why 存 SCC 用栈？

    环顶先访问，其余 SCC 的点后访问。绕环走一圈回到环顶，即环顶的函数空间即将退出时，栈内已逆序存储了 SCC 内所有点。此时，弹出并记录即可。

    本质：DFS 就是栈的先进后出思想体现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> g[M];
stack<int> s;
int n,m,cnt,tot;                                
int scc[N],siz[N],dfn[N],low[N];
void tarjan(int u)
{        
	dfn[u]=low[u]=++tot;
	s.push(u);	
	for(int v:g[u])
	{
		if(!dfn[v])  
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!scc[v]) low[u]=min(low[u],dfn[v]);
		/*debug1:+if(*) 去掉这个条件会导致有两个连通块的话，只有先dfs的那个答案是对的。设连通块b1,b2。
若b2→b1,就会用b1的dfn来更新b2的low，导致low值变小。让每个连通块dfs前重新更新dfn就行 if(!dfn[i]) tot=0,tarjan(i);不行 并不保证b2的dfn一定比b1的low小*/
	}	
	if(dfn[u]==low[u])//u为环顶
	{
		int x;cnt++;
		do{ //直接用while会导致少了最后一次循环,环顶u无法弹出
			x=s.top();
			s.pop(); 
			scc[x]=cnt;
			siz[cnt]++;
		}while(x!=u);//debug2.(segf) s.top()!=u ×s.pop()后top()!=x 
	}														
}

SCC 缩点

其实就是 SCC 的应用。将每个 SCC 缩成点，原图就变成了 DAG，有关于出入度等特殊性质。

P3387 【模板】缩点

直接进行 DFS 的话，就会在环那里转圈耗时过长（因为可重复经过，不能用 vis 标记）。类似题有 DAG 的最长路径，一个做法利用其无后效性 DP。如何将该题的有环图 $\to$ 无环图？缩点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=1e5+5;
vector<int> g[M];
vector<int> e[M];
stack<int> s;	
int n,m,cnt,tot;
int dfn[N],low[N],w[N],dp[N],scc[N],a[N];
void tarjan(int x)//debug:厌氧 考虑UB... int tarjan × 
{
	dfn[x]=low[x]=++tot;
	s.push(x);
	for(int y:g[x])
	{
		if(!dfn[y]) 
		{
			tarjan(y);
			low[x]=min(low[y],low[x]);
		}
		else if(!scc[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		int y;cnt++;
		do{
			y=s.top();s.pop();
			scc[y]=cnt;
			w[cnt]+=a[y];
		}while(y!=x);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) 
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back({y});
	}
	for(int i=1;i<=n;i++)//debug: n m不分。。
	{
		if(!dfn[i]) /*tot=0,*/tarjan(i);
	}
	//缩点 
	for(int u=1;u<=n;u++)
	{
		for(int v:g[u])
		{
			if(scc[v]!=scc[u]) e[scc[u]].push_back({scc[v]});
		}
	} 
	for(int u=cnt;u>=1;u--)//因为tarjan求出的SCC是逆DFS序的，所以这里要逆序dp从起点出发 
	{
		if(!dp[u]) dp[u]=w[u];//u为起点
		//else × 否则任意dp[u]=0
		for(int v:e[u]) 
		    dp[v]=max(dp[u]+w[v],dp[v]);
	}		
	for(int u=1;u<=cnt;u++)  dp[0]=max(dp[0],dp[u]);
    cout<<dp[0]; 
 	return 0;
}

边双连通分量（eDCC）

边双连通图：不含割边的无向连通图。

边双连通分量：极大边双连通子图。极大 $:=$ 不存在完全包含该图（点和边）的边双连通子图。

定理

$$
\text{边双连通图} \iff \forall e,\ e \in \text{简单环（不自交的环）}
$$

证明：

  • 充分性：$\forall x,y \in V$，$(x,y)$ 有 2 条。删除任意一条边，$(x,y) \ge 1$ 条，不符合割边定义。
  • 必要性：不含割边，即 $\forall x,y \in V$，$(x,y)$ 至少有 2 条（否则路径上所有边都为割边），显然满足环的定义。

算法：类似 SCC。由定理，其实就是在无向图上求环。

  • why 排除反边？

    注意到如果能走反边，任意两个相连的点都成了有向图意义下的环，当然不行。

    （这点使得代码类似 SCC + 割边）

P8436 【模板】边双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5*1e5+5,M=2*1e6+5;
vector<pair<int,int> > e;//注意存图方式 e存边
vector<int> g[N];//g存节点→对应边的序号
stack<int> s;
vector<int> edcc[N];//编号→包含的点
int n,m,tot,cnt,dfn[N],low[N];
void tarjan(int x,int in_edge)
{
	dfn[x]=low[x]=++tot;
	s.push(x);
	for(int id:g[x])
	{
		int y=e[id].second;
		if(!dfn[y])
		{
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
		}
		else if(id!=(in_edge^1)) low[x]=min(low[x],dfn[y]);//排除反边
	}
	if(dfn[x]==low[x])//环顶 
	{
		int y;cnt++;
		do{
			y=s.top();s.pop();
			edcc[cnt].push_back(y); 
		}while(y!=x);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		e.push_back({y,x}),g[y].push_back(e.size()-1);
		e.push_back({x,y}),g[x].push_back(e.size()-1);
	}
	for(int i=1;i<=n;i++) 
	    if(!dfn[i]) tarjan(i,0);
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++)
	{
		cout<<edcc[i].size();
		for(int u:edcc[i]) cout<<' '<<u;
		cout<<'\n';
	}
	return 0;
}

eDCC 缩点

SCC 缩点，得到 DAG。

eDCC 缩点 $\to$ 树/森林（因为满足每两个点间存在唯一路径）。

利用树的性质构造答案。

P2860 [USACO06JAN] Redundant Paths G

路径问题，考虑边双缩点。由定理，eDCC 里的不用加边，只需考虑割边。

问题转化为：树 $\to$ 每个点 $\in$ 一个简单环 的最短加边数。
连接叶子节点，可以连接在它上面的所有点形成环，显然最优。
对树的叶子节点数分奇偶讨论，尽可能两两配对，画几个图找规律即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//链式前向星写法 判反边稍微简单一些
#include<bits/stdc++.h>
#define  f(i,l,r) for(int i=l;i<=r;i++)
#define N 10000+5
using namespace std;
int n,m,cnt,num;
int ver[2*N],nxt[2*N],head[2*N],tot=1;//debug:从2，3开始配对 因为0号边被占用了 1^1=0
int dfn[N],low[N],deg[N],c[N];
bool bri[N];
stack<int> s;
//vector<int> edcc[N];
void add(int x,int y)
{ 
	ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void tarjan(int x,int e)
{
	dfn[x]=low[x]=++cnt;
	s.push(x);
	for(int i=head[x]/*,y=ver[i]*/;i;i=nxt[i])//debug:在for里只能定义初始值
	{
		int y=ver[i];
		if(!dfn[y])
		{
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;
		}
		else if(i!=(e^1)) low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])//环顶
	{
		int y;++num;
		do{
			y=s.top();
			s.pop();
			//edcc[num].push_back(y);
			c[y]=num;
		}while(y!=x);
	}
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin>>n>>m;
	f(i,1,m)	
	{
		int x,y;
		cin>>x>>y;
		add(x,y),add(y,x);
	}
//	f(i,1,n) debug2:每对草场之间已经有至少一条路径 保证联通图
//		if(!dfn[i]) 
	tarjan(1,0);
	for(int i=2;i<=tot;i+=2)
		if(bri[i]) deg[c[ver[i]]]++,deg[c[ver[i^1]]]++;
	int sum=0;
	f(i,1,num)
	{
		if(deg[i]==1) sum++;//统计叶子节点数
	}
	cout<<(sum+1)/2;
	return 0;
}

点双连通分量（vDCC）

类比边双定义：

  • 点双连通图：不含割点的无向连通图。
  • 点双连通分量（vDCC）：极大点双连通子图。

Thm1 任意割点 $\in$ 至少 2 个 vDCC 中（裂点）

证明：去掉任意一个割点 $x$，图至少会分裂成两个连通子图。每个连通子图去掉自己的割点，直接与割点 $x$ 相连的部分显然可以合并成一个 vDCC。

Lemma 2 个 vDCC 至多 1 个公共点

证明：若 2 个，则 2 个点都可作为割点，可以合并成一个 vDCC。

Thm2 非割点最多只在一个点双连通分量内

证明：反设只有（Lemma）一个非割点 $x$ 在 2 个 vDCC 中。由于非割点，去掉 $x$ 后 2 个 vDCC 仍连通，可以合并。矛盾。

Thm3 一张无向图是点双连通图，当且仅当满足下列两个条件之一：

(1) 图的顶点数不超过 2；

(2) 图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环，也就是我们通常画出的环。

证明：

（1）显然。

（2）充分性：有环就有两条路，使一条路上割掉点 $p$，两点仍以另一条连通。排除 $p$ 是割点。

必要性：反证法。

  1. 不是环？$(x,y)$ 要是一条路，路上都是割点。
  2. 自交？交点成割点。

关于根节点的入栈问题解释

关于出栈另一种写法的问题解释

算法：

  1. 进栈；
  2. dfn[x] <= low[y]，则 x 为割点/根节点。由 Thm1，找 y 为环顶的 vDCC（具体就是弹出节点，直至 y 被弹出）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5*1e5+5,M=2*1e6+5;
vector<int> g[N];
stack<int> s;
vector<int> vdcc[N];
int n,m,tot,cnt,root,cv[N],dfn[N],low[N];
void tarjan(int x)//由Thm3,vDCC有环,所以可以用low等信息
{
	dfn[x]=low[x]=++tot;
	s.push(x);
	if(!g[x].size())//孤立点 由Thm3(1),一定点双
	{
		vdcc[++cnt].push_back(x);
		return;
	}
	for(int y:g[x])
	{
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
    		if(dfn[x]<=low[y])//判割点 
    		{
    			int t;cnt++;
    			do{
    				t=s.top();s.pop();//由Thm2,直接出栈
    				vdcc[cnt].push_back(t); 
    			}while(t!=y);
    			vdcc[cnt].push_back(x);//x割点：由Thm1裂点，加入多个vdcc,不能出栈.
    		}
		}
		else  low[x]=min(low[x],dfn[y]);//无if?由Thm3(1),可走反边,2点也成vDCC
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		if(x==y) continue;//debug1:判重边（普通重边对答案无贡献，自环则dfn[x]!=0无法进行出栈过程）
		g[x].push_back({y});
		g[y].push_back({x});
	}
	for(root=1;root<=n;root++) 
	    if(!dfn[root]) tarjan(root);
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++)
	{
		cout<<vdcc[i].size();
		for(int u:vdcc[i]) cout<<' '<<u;
		cout<<'\n';
	}
	return 0;
}

典例

P7687 [CEOI2005] Critical Network Lines

删掉该路图会不连通，所以为割边。筛出符合的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5;
vector<int> g[N];
vector<pair<int,int> > e;
int n,m,k,l,tot,cnt;
int low[N],dfn[N],cv[N],cnl[M],a[N],b[N];
void add(int x,int y)
{
	e.push_back({x,y});
	g[x].push_back(e.size()-1);
}
void tarjan(int x,int in_edge)
{
	dfn[x]=low[x]=++tot;
	for(int id:g[x])
	{
		int y=e[id].second;
		if(!dfn[y])
		{
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y]) 
			{
			    //cout<<dfn[x]<<' '<<low[y]<<endl;
			    //cout<<x<<' '<<y<<' '<<a[y]<<' '<<b[y]<<endl;
				if(!a[y]||!b[y]||a[y]==k||b[y]==l) cnl[++cnt]=id;//如果搜索子树里全是特殊点/子树里无特殊点 ，此时图就会分成两个连通块，不含特殊点的就无法访问服务
			}
			a[x]+=a[y];b[x]+=b[y];//向上更新特殊点个数
		}
		else if(id!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>l;
	for(int i=1;i<=k;i++)
	{
		int x;  
		cin>>x;
		a[x]=1;
	}
	for(int i=1;i<=l;i++)
	{
		int x;
		cin>>x;
		b[x]=1;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y),add(y,x);
	}
	tarjan(1,0);
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++)
		cout<<e[cnl[i]].first<<' '<<e[cnl[i]].second<<'\n';
 	return 0;
}

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

喜欢它等价于可达它。

任意一个 SCC 内点都是互相可达的，属于同一类点。真正的三角恋

考虑缩点，那么 Cow Star 显然就是新图唯一的叶子结点（出度为 0）。因为每个新点都可到达它。

不唯一则叶子结点间不互相可达。无 cow star。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
vector<int> g[N];
vector<int> e[N];
stack<int> s;
int n,m,cnt,tot;
int dfn[N],low[N],scc[N],siz[N],deg[N];//deg：缩点后出度 
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	s.push(x);
	for(int y:g[x])
	{
	    if(!dfn[y])
	    {
	        tarjan(y);
		    low[x]=min(low[x],low[y]);
	    }
	    else if(!scc[y]) low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{	
		int y;cnt++;
		do{
			y=s.top();s.pop();
			scc[y]=cnt;
			siz[cnt]++;
		}while(y!=x);
	}
}   
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
	}
	//tarjan(1);
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) 
		{
		    tarjan(i);
			//cout<<0;	别像我一样想当然以为这样判出不连通就输出0. 因为1也可能是明星...
			//return 0;
		}
	}
	for(int x=1;x<=n;x++)//缩点后统计出度
	{
		for(int y:g[x])
		{
			int a=scc[x],b=scc[y];
			if(a!=b) deg[a]++;
		}
	}	
	int ans=0,ed=0;//ans:叶子节点数，ed：叶子结点编号
	for(int i=1;i<=cnt;i++)
		if(!deg[i]) ed=i,ans++;
	if(ans>1) cout<<0;
	else cout<<siz[ed];
 	return 0;
}