【基础练习】【强连通tarjan】vijos1021-1023 Victoria的舞会系列题解

痛定思痛。 2022-08-09 09:59 15阅读 0赞

题目连接：[**https://vijos.org/p/Victoria%E7%9A%84%E8%88%9E%E4%BC%9A**][https_vijos.org_p_Victoria_E7_9A_84_E8_88_9E_E4_BC_9A]

这是一个图论的系列题目，题目比较简单，主要在于数据实在是弱···两百个点暴搜都能过啊···

vijos用户体验还是不错的 除了管理不太严格导致题解混乱 虽然二老板在但也长期无人打理  如果照管好 这一定会是一个相当出色的OJ

1021 舞会1

这道题目其实就是简单的统计 不多说 上代码

//vijos1021 Victoria的舞会1 模拟
    //copuright by ametake
    #include
       
        
    using namespace std;
    
    int a[200+10];
    int n,k,m;
    
    int main()
    {
        scanf("%d%d",&n,&k);
        int x=0;
        for (int i=1;i<=n;i++)
        {
            while (scanf("%d",&x)&&(x!=0)) a[i]++;
            if (a[i]>=k) m++;
        }
        printf("%d\n",m);
        return 0; 
    }

1022 舞会2

由于交流具有传递性 每个小组都是一个尽可能大的环 直接统计强连通分量个数即可

//vijos1022 Victoria的舞会2 tarjan
    //copuright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=200+10;
    const int maxm=40000+10;
    int n,m=0;
    int hd[maxn],tt[maxm*2],nxt[maxm*2],et=0;
    int dfn[maxn],low[maxn],sta[maxn],stp=0,dep=0;
    bool ins[maxn];
    
    inline int read()
    {
        int a=0;
        char ch=getchar();
        while (ch<'0'||ch>'9')
        {
            ch=getchar();
        }
        while (ch>='0'&&ch<='9')
        {
            a=a*10+ch-'0';
            ch=getchar();
        }
        return a;
    }
    
    void add(int x,int y)
    {
        et++;
        tt[et]=y;
        nxt[et]=hd[x];
        hd[x]=et;
    }
    
    void tarjan(int x)
    {
        dfn[x]=low[x]=++dep;
        ins[x]=true;
        sta[++stp]=x;
        for (int i=hd[x];i!=0;i=nxt[i])
        {
            if (!dfn[tt[i]])
            {
                tarjan(tt[i]);
                low[x]=min(low[x],low[tt[i]]);
            }
            else if (ins[tt[i]])
            {
                low[x]=min(low[x],dfn[tt[i]]);
            }
        }
        if (dfn[x]==low[x])
        {
            int j;
            m++;
            do
            {
                j=sta[stp--];
                ins[j]=false;
            }while (j!=x);
        }
        return;
    }
    
    int main()
    {
        n=read();
        for (int i=1;i<=n;i++)
        {
            int x=read();
            while (x)
            {
                add(i,x);
                x=read();
            }
        }
        for (int i=1;i<=n;i++)
        {
            if (!dfn[i])
            {
                tarjan(i);
            }
        }
        printf("%d\n",m);
        return 0;
    }

1023 舞会3

这道题目做法很多样 虽然题解里说数据弱到粘第二题代码都能过（太坑了吧！难道不存在一条链的情况吗？！）但我还是老实写了强连通缩点+统计入度

我们考虑什么样的情况可以不用通知呢？一个是环，因为环内人可以互相通知，只需通知一个人就可以了，因此可以缩成一点；另一个是链，链起始点的人可以通知到这条链上所有人。

因此，做一次tarjan之后统计出度为0的节点就可以了。但不知为什么，同样的方法间谍网络就T了= =

代码：

//vijos1023 Victoria的舞会3 tarjan
    //copuright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=200+10;
    const int maxm=40000+10;
    int n,m=0,ans=0;
    int hd[maxn],tt[maxm*2],nxt[maxm*2],et=0;
    int dfn[maxn],low[maxn],sta[maxn],stp=0,dep=0;
    bool ins[maxn],ru[maxn][maxn];
    int inwhich[maxn],rudu[maxn];
    
    inline int read()
    {
        int a=0;
        char ch=getchar();
        while (ch<'0'||ch>'9')
        {
            ch=getchar();
        }
        while (ch>='0'&&ch<='9')
        {
            a=a*10+ch-'0';
            ch=getchar();
        }
        return a;
    }
    
    void add(int x,int y)
    {
        et++;
        tt[et]=y;
        nxt[et]=hd[x];
        hd[x]=et;
    }
    
    void tarjan(int x)
    {
        dfn[x]=low[x]=++dep;
        ins[x]=true;
        sta[++stp]=x;
        for (int i=hd[x];i!=0;i=nxt[i])
        {
            if (!dfn[tt[i]])
            {
                tarjan(tt[i]);
                low[x]=min(low[x],low[tt[i]]);
            }
            else if (ins[tt[i]])
            {
                low[x]=min(low[x],dfn[tt[i]]);
            }
        }
        if (dfn[x]==low[x])
        {
            int j;
            m++;
            do
            {
                j=sta[stp--];
                ins[j]=false;
                inwhich[j]=m;
            }while (j!=x);
        }
        return;
    }
    
    int main()
    {
        n=read();
        for (int i=1;i<=n;i++)
        {
            int x=read();
            while (x)
            {
                add(i,x);
                x=read();
            }
        }
        for (int i=1;i<=n;i++)
        {
            if (!dfn[i])
            {
                tarjan(i);
            }
        }
        for (int i=1;i<=n;i++)
        {
            for (int j=hd[i];j!=0;j=nxt[j])
            {
                if ((inwhich[i]!=inwhich[tt[j]])&&(!ru[inwhich[i]][inwhich[tt[j]]]))
                {
                    ru[inwhich[i]][inwhich[tt[j]]]=true;
                    rudu[tt[j]]++;
                }
            }
        }
        for (int i=1;i<=m;i++) if (rudu[i]==0) ans++;
        printf("%d\n",ans);
        return 0;
    }

——东篱把酒黄昏后，有暗香盈袖

[https_vijos.org_p_Victoria_E7_9A_84_E8_88_9E_E4_BC_9A]: https://vijos.org/p/Victoria%E7%9A%84%E8%88%9E%E4%BC%9A