poj 2186 强连通分量缩点+判断出度

旧城等待， 2022-08-20 06:16 137阅读 0赞

***Popular Cows***

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 28426</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 11508</td> 
  </tr> 
 </tbody> 
</table>

Description

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is  
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

Input

\* Line 1: Two space-separated integers, N and M  
  
\* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

\* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

3 3
    1 2
    2 1
    2 3

Sample Output

Hint

Cow 3 is the only cow of high popularity.

题意: 给定一个有向图, 求能被其余所有的点到达的点的数目;

分析: 缩点之后统计每个分块的出度, 如果出度大于1 ,答案肯定是0 ,因为出度为零的点不能相互到达, 如果出度为零的分块是1个, 那么答案就是这个分块的点的数目, 因为除了这个分块其余每个分块都有出度, 相当于一个个漏斗, 往这里面倒水, 肯定都跑到出度为零的分块中, 因此每个分块都能到达出度为零的分块.

开始是用拓扑排序做的, 从入度为零的点逐渐往上更新, 最后判断入度为n的分块;

//强联通分量的缩点 + 拓扑排序
    #include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=10010;
    
    int n,m,dfn[N],low[N],dfs_num,cnt,Stack[N],top,deg[N],scc[N],num[N],rd[N];
    vector<int> v[N],G[N];
    set<pii> s;
    void init()
    {
        s.clear();
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
            G[i].clear();
            num[i]=0;
            deg[i]=0;
            dfn[i]=0;
            rd[i]=0;  //
            scc[i]=0;  //
            //low[i]=0;
        }
        dfs_num=0;
        cnt=0;
        top=0;
    }
    
    void tarjan(int x)
    {
        low[x]=dfn[x]=++dfs_num;
        Stack[++top]=x;
        for(int i=0;i<(int)v[x].size();i++)
        {
            int t=v[x][i];
            if(!dfn[t])
            {
                tarjan(t);
                low[x]=min(low[x],low[t]);
            }
            else if(!scc[t] && dfn[t] < low[x])  //
            {
                low[x] = dfn[t];
            }
        }
        if(low[x] == dfn[x])
        {
            cnt++;
            while(1)
            {
                int t=Stack[top--];
                scc[t]=cnt;
                if(x==t) break;
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            init();
            for(int i=0;i<m;i++)
            {
                int x=in(),y=in();
                v[x].push_back(y);
            }
            for(int i=1;i<=n;i++)  //
            {
                if(!dfn[i]) tarjan(i);
            }
            for(int i=1;i<=n;i++)
            {
                rd[scc[i]]++;
                num[scc[i]]++;
            }
            for(int i=1;i<=n;i++)
            {
                int x=scc[i];
                for(int j=0;j<(int)v[i].size();j++)
                {
                    int y=scc[v[i][j]];
                    if(x==y || s.find(pii(x,y)) != s.end()) continue;
                    deg[y]++;   //
                    s.insert(pii(x,y));
                    G[x].push_back(y);
                }
            }
            int ans=0;
            queue<int> q;
            for(int i=1;i<=cnt;i++)
            {
                if(deg[i]==0) q.push(i);
            }
            while(!q.empty())
            {
                int now = q.front();
                q.pop();
                for(int i=0;i<(int)G[now].size();i++)
                {
                    int t=G[now][i];
                    deg[t]--;
                    if(deg[t]==0)
                    {
                        q.push(t);
                    }
                    rd[t] += rd[now];
                }
            }
            //cout<<cnt<<endl;
            for(int i=1;i<=cnt;i++)
            {
                if(rd[i]==n) ans += num[i];
            }
            printf("%d\n",ans);
        }
        return 0;
    }

判断出度的:

//强联通分量缩点 + 判断分块的出度为0的个数
    #include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=10010;
    
    int n,m,dfn[N],scc[N],Stack[N],low[N],dfs_num,top,cnt,cd[N];
    vector<int >v[N];
    void init()
    {
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
            cd[i]=0;
            dfn[i]=0;
            //low[i]=0;
            scc[i]=0;
        }
        top=0;
        cnt=0;
        dfs_num=0;
    }
    
    void tarjan(int x)
    {
        dfn[x]=low[x]=++dfs_num;
        Stack[++top]=x;
        for(int i=0;i<v[x].size();i++)
        {
            int t=v[x][i];
            if(!dfn[t])
            {
                tarjan(t);
                low[x]=min(low[x],low[t]);
            }
            else if(!scc[t])
            {
                low[x]=min(low[x],dfn[t]);
            }
        }
        if(dfn[x] == low[x])
        {
            cnt++;
            while(1)
            {
                int t=Stack[top--];
                scc[t]=cnt;
                if(x==t) break;
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            init();
            for(int i=0;i<m;i++)
            {
                int x=in(),y=in();
                v[x].push_back(y);
            }
            for(int i=1;i<=n;i++)
            {
                if(!dfn[i]) tarjan(i);
            }
            for(int i=1;i<=n;i++)
            {
                int x=scc[i];
                for(int j=0;j<v[i].size();j++)
                {
                    int y=scc[v[i][j]];
                    if(x==y) continue;
                    cd[x]=1;
                    break;
                }
            }
            int ans=0,c=0;
            for(int i=1;i<=cnt;i++)
            {
                if(cd[i]==0)
                {
                    if(c)
                    {
                        ans=0;
                        break;
                    }
                    c++;
                    ans=i;
                }
            }
            if(ans==0)
            {
                puts("0");
                continue;
            }
            int ret=0;
            for(int i=1;i<=n;i++)
            {
                if(scc[i]==ans) ret++;
            }
            printf("%d\n",ret);
        }
        return 0;
    }