算法 图的应用 算法算法C/C++

1. 谁是“大腿”？
   【问题描述】

N名小朋友要组队踢球。小朋友都想和球踢得好的”大腿“一个队。小朋友们都有自己心中的”大腿“，用M对整数(x, y)表示x认为y是”大腿“。 此关系是可传递的，即：若x认为y是大腿、y认为z是大腿，则x认为z是大腿。

你的任务是求出被所有其他小朋友认为是大腿的有多少个？

小朋友的编号从1开始到N，N不超过2万，M不超过10万。

【输入形式】

第一行两个数N和M。

接下来M行，每行两个由空格分隔的整数x和y，表示x认为y是大腿。

【输出形式】

一个整数，表示被其他所有小朋友认为是“大腿”的数量。

【样例输入】

3 3

2 3

3 2

1 2

【样例输出】

2

【样例说明】

1认为2、3是大腿，2、3互认对方是大腿，因此有2个（2和3）被其他所有（1号小朋友）认为是大腿。

#include <bits/stdc++.h>

using namespace std;
const int N=5e4+5;
int n,m,dfn[N],vis[N],low[N],t=0,num=0,b[N],cnt[N];
int x[N],y[N],out[N];
vector<int> a[N];
stack<int> s;

void dfs(int x)
{
    dfn[x]=low[x]=++t;
    s.push(x);
    vis[x]=1;
    for(int i=0;i<a[x].size();i++)
    {
        int y=a[x][i];
        if(!dfn[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y])
            low[x]=min(low[x],low[y]);
    }
    if(low[x]==dfn[x])
    {
        num++;
        while(s.top()!=x)
        {
            b[s.top()]=num;//编号
            cnt[num]++;
            vis[s.top()]=0;
            s.pop();
        }
        b[x]=num;
        cnt[num]++;
        vis[x]=0;
        s.pop();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    //cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        //cin >> x[i] >> y[i];
        a[x[i]].push_back(y[i]);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(i);
    for(int i=0;i<m;i++)//新建图，缩点
    {
        int x0=b[x[i]],y0=b[y[i]];
        if(x0!=y0)
            out[x0]++;
    }
    int res=0,x=0;
    for(int i=1;i<=num;i++)
    {
        if(out[i]==0)
        {
            x=i;
            res++;
        }
        if(res>1)
        {
            printf("0\n");
            return 0;
        }
    }
    printf("%d\n",cnt[x]);
    return 0;
}