https://www.luogu.com.cn/problem/P1262

间谍网络
关键在缩点的时候选择性的tarjan
只会搜搜得到的点

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
unordered_map<string,int>cou;
const int N =100005, M=5e5+10;
int n,m;
int h[N], e[M], ne[M], idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt;
int din[N],dout[N];
int w[N]; 
int minn[N],sum[N],minid[N];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for (int i = h[u]; ~i ; i =ne[i] ){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(in_stk[j]) {//搜过了 说明是回去的边
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
			if(w[y]<minn[scc_cnt]){
				minn[scc_cnt]=w[y];
			}
			
						
        }while(y!=u);
        
    }
}
int main()
{
    cin>>n;
	cin>>m;
    memset(h, -1, sizeof h);
    memset(w,0x3f,sizeof w);
    memset(minid,0x3f,sizeof minid);
    memset(minn,0x3f,sizeof minn);
    int x,y;
    while(m--){
    	cin>>x>>y;
		w[x]=y;	
	}
    cin>>m;
    for (int i = 1; i <= m; i ++ ){
        cin>>x>>y;
        if(x!=y)//用来处理自环 
        add( x,y );
    }
    
    for (int i = 1; i <= n; i ++ )//tarjan 遍历所有点 所以是2*n 
    if(!dfn[i]&&w[i]!=0x3f3f3f3f)//能买才以这个起点找这个环 
    tarjan(i);//因此没有dfn的就是不能买的点 
    
    for(int i=1;i<=n;i++)      //在这里我们用dfn数组来判断它是否被遍历过 
	if(!dfn[i])
	{
		printf("NO\n");
		printf("%d\n",i);
		return 0;
	}
    
    
    int cnt=0;
    
    for(int i=1;i<=n;i++){
    	for(int j=h[i];~j;j=ne[j]){
    		int k=e[j];
    		int a=id[i],b=id[k];
    		if(a!=b){
    			din[b]++;
			}
		}
	} 
	
    int res=0;
    for(int i=1;i<=scc_cnt;i++){
    
    	if(!din[i]&&minn[i]!=0x3f3f3f3f){
    		res+=minn[i];
		}
	}

	cout<<"YES"<<endl;	
	cout<<res<<endl;
	

    return 0;
}