P2863 [USACO06JAN]牛的舞会The Cow Prom

左手的ㄟ右手 2023-08-17 16:15 82阅读 0赞

*  链接
 *  思路
 *  代码
 *  错误原因

# 链接 #

[P2863 \[USACO06JAN\]牛的舞会The Cow Prom][P2863 _USACO06JAN_The Cow Prom]

# 思路 #

用$tarjan$求出强连通分量，并且记录出强连通分量里的点的个数，如果个数大于$1$就$ans++$

# 代码 #

#include<bits/stdc++.h>
    #include<vector>
    #include<stack>
    using namespace std;
    const int N=50010;
    int dfn[N],low[N],sum,top,vis[N],col[N];
    vector<int>g[N];
    stack<int> q;
    int num2;
    int ans;
    int tot[N];
    int n,m,dep;
    void tarjan(int u) {
        ++dep;
        dfn[u]=low[u]=dep;
        q.push(u);
        vis[u]=1;
        int len=g[u].size();
        for(int i=0; i<len; ++i) {
            int v=g[u][i];
            if(!dfn[v]) {
                tarjan(v);
                low[u]=min(low[u],low[v]);
            } else {
                if(vis[u]) low[u]=min(low[u],low[v]);
            }
        }
        if(dfn[u]==low[u])//找到强联通分量了
        {
            sum++;
            num2++;
            col[u]=sum;
            vis[u]=0; 
            tot[num2]++;
            while(q.top()!=u)
            {
                int Top=q.top();
                q.pop();
                col[Top]=sum;
                tot[num2]++;
                vis[Top]=0;
            }
            q.pop();
        }
    }
    signed main() {
        cin>>n>>m;
        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)
            //if(!col[i]) tarjan(i);
            if(!dfn[i]) tarjan(i);
        for(int i=1;i<=num2;++i) 
            if(tot[i]>1) ans++;
        cout<<ans;
        return 0;
    }

# 错误原因 #

if(dfn[u]==low[u])//找到强联通分量了
        {
            sum++;
            num2++;
            col[u]=sum;
            vis[u]=0; 
            tot[num2]++;//没有这一句
            while(q.top()!=u)
            {
                int Top=q.top();
                q.pop();
                col[Top]=sum;
                tot[num2]++;
                vis[Top]=0;
            }
            q.pop();
        }

少算了割点

转载于:https://www.cnblogs.com/pyyyyyy/p/11356931.html

[P2863 _USACO06JAN_The Cow Prom]: https://www.luogu.org/problem/P2863