Tarjan缩点第一题……

很容易想到找出度为0的点（当且仅当这样的点有一个时有解），但是在有环图上这个方法会失效。

处理方法是，用Tarjan的强联通分量算法求出所有SCC，然后把每个SCC缩成一个点，然后再在缩点之后的图上求解即可（这个图是DAG。原因很简单，要是有环还能接着缩）。

代码：

/**************************************************************
    Problem: 1051
    User: danihao123
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:1692 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
    dfs_clk++;
    pre[x]=low[x]=dfs_clk;
    S.push(x);
    int i,u;
    for(i=first[x];i;i=next[i]){
        u=to[i];
        if(!pre[u]){
            dfs(u);
            low[x]=min(low[x],low[u]);
        }else{
            if(!sccno[u])
                low[x]=min(low[x],pre[u]);
        }
    }
    if(low[x]==pre[x]){
        scc_cnt++;
        sccsiz[scc_cnt]=0;
        while(true){
            u=S.top();
            S.pop();
            sccno[u]=scc_cnt;
            sccsiz[scc_cnt]++;
            if(u==x)
                break;
        }
    }
}
int n;
inline void Tarjan(){
    register int i;
    for(i=1;i<=n;i++)
        if(!pre[i])
            dfs(i);
}
 
bool Out[maxn];
int main(){
    int m,u,v;
    register int i,j,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    Tarjan();
    for(i=1;i<=n;i++){
        for(j=first[i];j;j=next[j]){
            u=to[j];
            if(sccno[i]!=sccno[u])
                Out[sccno[i]]=true;
        }
    }
    for(i=1;i<=scc_cnt;i++){
        if(!Out[i]){
            if(ans){
                ans=0;
                break;
            }
            ans=sccsiz[i];
        }
    }
    if(n==1)
        ans=0;
    printf("%d\n",ans);
    return 0;
}

• 相关文章
• 全局相关文章