注意到一个两个点都能互相到达的连通块内，所有点能到达点数相同，先将有向图缩个点试试。

根据题意，缩完只会得到一个有向无环图 DAG，考虑在这个图上得到贡献。

而且 DAG 图一定是公平的，也就是一个点到另外一个最多只有一条路径，即遍历到这个点时只会来自不同且不相连的点。

这样我们就可以愉快的 01 dfs 了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5e4 + 10;
vector<int> G[N]; 
bool v[N]; stack<int> sta;
int dfn[N], low[N], tsp, cnt, scc[N], siz[N];

void tarjan(int x) {
    dfn[x] = low[x] = ++tsp; 
	v[x] = 1; sta.push(x);
    for (auto y: G[x]) {
        if (!dfn[y]) {
            tarjan(y); 
            low[x] = min(low[x], low[y]);
        }
        else if(v[y]) low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x]) {
        cnt ++; int y = sta.top();
        siz[cnt] = 0;
        while(y != x){
            v[y] = 0; sta.pop();
            scc[y] = cnt;  y= sta.top();
            siz[cnt] ++;
        }
        sta.pop(); scc[x] = cnt; v[x] = 0;
        siz[cnt] ++;
    }
}

vector<int> E[N];
int d[N], in[N];
queue<int> Q;

void dfs(int x) {
	v[x] = 1;
	for (int y : E[x]) {
		if (!v[y]) dfs(y);
		siz[x] += siz[y];
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
    int n, m; 
    cin >> n >> m;
    memset(G, 0, sizeof(G));
    for(int i = 1; i <= m; i ++){
        int x, y; 
        cin >> x >> y;
        G[x].push_back(y);
    }
    
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    
    tsp = 0; memset(v, 0, sizeof(v));
    cnt = 0;
    for (int i = 1; i <= n; i ++) if(!dfn[i]) tarjan(i);
    
    memset(in, 0, sizeof(in));
	for (int i = 1; i <= n; i ++) {  
	    for (int j : G[i]) if(scc[i] != scc[j]) {
		   	E[scc[i]].push_back(scc[j]);  
		   	in[scc[j]] ++;
		}
	} 
	memset(v, 0, sizeof(v));
	for (int i = 1; i <= cnt; i ++) if (!in[i]) {
		dfs(i);
	}
	
    
    for (int i = 1; i <= n; i ++) {
    	cout << siz[scc[i]] - 1 << "\n";
	}
    
    return 0;
}

P12760 解题报告

这是一篇不需要注意力的题解

这题有点新，没什么人做，正好最近在练习 tarjan，就写一篇题解来巩固一下。刷估值

前置知识：tarjan 求 scc，缩点。

如果不会：【模板】缩点

首先，不难发现，在同一个连通块中，所有节点的答案相同。所以便有了缩点的想法。

缩点之后怎么办呢？注意到缩点之后的图一定是 DAG（有向无环图）就可以愉快地打记搜了。

虽然由题设可知，缩点之后的图是一颗树，相比于 DAG，树的条件显然更强，但是我们记搜只需要 DAG。终于不需要注意力了

关于记搜的实现：回溯的时候进行转移 不难得到转移方程：

初始化如下

$scc$ 就是强联通分量大小。

注意一下节点本身不加入计数，下面就是喜闻乐见的 AC 环节。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4;
int n,m;
vector <int> g[N + 5],_g[N + 5];
int dfn[N + 5],low[N + 5];
int cnt;
stack <int> st;
bool inst[N + 5];
int cnte;
int belong[N + 5];
vector <vector <int> > scc;
void tarjan(int x,int fa){
	dfn[x] = low[x] = ++cnt;
	st.push(x);
	inst[x] = true;
	for(auto it : g[x]){
		if(!dfn[it]){
			tarjan(it,x);
			low[x] = min(low[x],low[it]);
		}else if(inst[it])
		    low[x] = min(low[x],dfn[it]);
	}
	if(dfn[x] == low[x]){
		vector <int> v;
		while(st.size() && st.top()!= x){
			v.push_back(st.top());
			inst[st.top()] = false;
			belong[st.top()] = cnte;
			st.pop();
		}
		v.push_back(x);
		inst[x] = false;
		belong[x] = cnte;
		st.pop();
		scc.push_back(v);
		cnte++;
	}
}
int dp[N + 5];
void dfs(int x){
	if(dp[x])
	    return;
	for(auto it : _g[x]){
		dfs(it);
		dp[x] += dp[it];
	}
	dp[x] += scc[x].size();
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i])
			tarjan(i,0);
	}
	for(int i = 0;i < cnte;i++)
		for(auto it : scc[i])
			for(auto j : g[it])
				if(belong[j] != i){
					_g[i].push_back(belong[j]);
				}
	for(int i = 0;i < cnte;i++)
		if(!dp[i])
			dfs(i);
	for(int i = 1;i <= n;i++)
	    cout << dp[belong[i]] - 1 << endl;
	return 0;
}