题目

分析

题目要求把图删点，删成树。

考虑一下树的定义，点数n=边数m+1

并且，树中点两两之间联通，那么选的点就不能是割点。

可以用tarjan将图中最大的联通块，保证其中点两两之间有不止一条路径来联通。

那么保证这个联通块中向外界联通的点一定是割点。

求出最大的联通块后，每个点判读一下就可以了。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=101000;

using namespace std;

int n,m,low[N],dfn[N],last[N],next[N*2],to[N*2],tot,d[N],b[N],dd;

bool bz[N],part[N];

int bj(int x,int y)

{

    next[++tot]=last[x];

    last[x]=tot;

    to[tot]=y;

}

int tarjan(int x,int fa)

{

    dfn[x]=low[x]=++dd;

    d[++tot]=x;

    bz[x]=false;

    for(int i=last[x];i;i=next[i])

    {

        int j=to[i];

        if(fa!=j)

        {

            if(bz[j])

            {

                tarjan(j,x);

                low[x]=min(low[x],low[j]);

            }

            else

                low[x]=min(low[x],low[j]);

        }

    }

    if(dfn[x]==low[x])

    {

        if(d[tot]==x)

            tot--;

                else

                    while(dfn[d[tot]]>=dfn[x])

                    {

                        part[d[tot--]]=true;

                    }

    }

}

int main()

{

    memset(bz,true,sizeof(bz));

    scanf("%d%d",&n,&m);

    if(m==n-1)

    {

        for(int i=1;i<=m;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            b[x]++;

            b[y]++;

        }

        int ans=0;

        for(int i=1;i<=n;i++)

            if(b[i]==1)

                ans++;

        printf("%d\n",ans);

        for(int i=1;i<=n;i++)

            if(b[i]==1)

                printf("%d ",i);

        return 0;

    }

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        bj(x,y);

        bj(y,x);

    }

    for(int i=1;i<=n;i++)

    {

        if(!last[i])

        {

            printf("1\n%d",i);

            return 0;

        }

    }

    tot=0;

    tarjan(1,0);

    memset(bz,false,sizeof(bz));

    int ans=0;

    for(int i=1;i<=n;i++)

    {

        if(part[i])

        {

            bz[i]=true;

            int sum=0;

            for(int j=last[i];j;j=next[j])

            {

                if(!part[to[j]])

                {

                    bz[i]=false;

                    break;

                }

                else sum++;

            }

            if(m-sum+1!=n-1) bz[i]=false;

            if(bz[i]) ans++;

        }

    }

    printf("%d\n",ans);

    for(int i=1;i<=n;i++)

        if(bz[i])

            printf("%d ",i);

}

巴特西

【NOIP2016提高A组8.11】种树

题目

分析

最新文章

热门文章