P2863 [USACO06JAN]The Cow Prom S(Tarjan)

思路： $Tarjan$ 模板题。

==注意==：不能根据 $s$ 的 $size$ 来判断连通块的大小。

举个例子 $2$ 个结点 $1,2$ ，一条边 $<1,2>$ 即 $1\rightarrow 2$

显然遍历到2时，此时栈中有 $1,2$ 两个数，但是 $low[2]=dfn[2]=2$ .会进入到涂色。但是只会涂一个点 $2$ ，因为它是孤立点。事实上可以有另外一种判断方法，因为某一个结点要么属于连通块，要么是一个孤立点，所以在判断时可以标记一下此时的 $size$ 是否大于1，然后看 $size$ 是否变为0了，如果变为0了说明属于一个大于1的连通块，否则是一个孤立结点，这种方法就不需要用到 $num,col$ 数组。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
#define mst(a) memset(a,0,sizeof a)
int n,m,dfn[N],low[N],id,vis[N],ans,col[N],num[N],sum=0;
vector<int>e[N];  //dfs[i]记录结点i遍历顺序,low[i]记录结点i及其子结点最小遍历顺序,vis[i]标记是否在栈中。 
stack<int>s;        //col[i]记录结点i属于那个连通块(本题没用),num[i]记录第i个连通块的结点数. 
void dfs(int u){
     dfn[u]=low[u]=++id;//记录dfs顺序 
     s.push(u);//入栈 
     vis[u]=1;//标记入栈. 
     for(auto v:e[u]){
          if(!dfn[v]){
                dfs(v); //没有遍历的点进行遍历然后更新low 
                low[u]=min(low[u],low[v]);
          }
          else if(vis[v]) low[u]=min(low[u],low[v]);//如果已经遍历过而且在栈中 则取low较小值(这里是潜在的连通块) 
     }
     if(dfn[u]==low[u]){ //该点是连通块的"根"  注意孤立点也是连通块. 
         vis[u]=0;   //回溯标记，并染色. 
         col[u]=++sum;
         num[sum]++;
         while(s.top()!=u){ //依次出栈. 
             col[s.top()]=sum;
              vis[s.top()]=0;
              s.pop();
              num[sum]++;
         }
         s.pop();
     }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
    } 
    for(int i=1;i<=n;i++)  
        if(!dfn[i]) dfs(i); //可能存在孤立点,所以要dfs所有可能点.    
    for(int i=1;i<=sum;i++)
        if(num[i]>1) ans++; 
    printf("%d\n",ans);
    return 0;
}

另一种判断方法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
#define mst(a) memset(a,0,sizeof a)
int n,m,s[N],dfn[N],low[N],id,top,vis[N],ans;
vector<int>e[N]; 
void dfs(int u){
     dfn[u]=low[u]=++id;
     s[++top]=u;
     vis[u]=1;
     for(auto v:e[u]){
          if(!dfn[v]){
                dfs(v);
                low[u]=min(low[u],low[v]);
          }
          else if(vis[u]) low[u]=min(low[u],low[v]);
     }
     if(dfn[u]==low[u]){
         vis[u]=0;
         int f=0;
         if(top>1) f=1;
         while(s[top]!=u){
              vis[s[top--]]=0;
         }
         top--;
         if(!top&&f) ans++;
     }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
    } 
    for(int i=1;i<=n;i++)
        if(!dfn[i]) dfs(i);    
    printf("%d\n",ans);
    return 0;
}