NOIp模拟赛18/7/20 种树 题解【tarjan】【割点】【树】

作者: wjyyy 分类: tarjan,割点,,解题报告 发布时间: 2018-07-20 20:22

点击量:23

 

   tarjan求割点的变形。

 

题目背景

\(\mathrm{Fanvree}\)很聪明,解决难题时他总会把问题简单化。

 

例如,他就整天喜欢把图转化为树。但是他不会缩环,那他怎么转化呢?

 

题目描述

这是一个有\(n\)个点\(m\)条双向边的图,\(\mathrm{Fanvree}\)会选定一个节点, 然后删掉这个节点和这个点连出去的边, 如果变成了一棵树, 那么这个节点便是可行的, 什么是树呢? 树也即无简单环的无向连通图。

 

告诉\(\mathrm{Fanvree}\)可能的节点是什么。

 

输入输出格式

输入格式:

第一行两个正整数\(n,m\),表示有\(n\)个点\(m\)条边。 保证\(n\ge 2\)。

 

接下来$vm$行, 每行两个整数\(v,u\),表示\(v\)和\(u\)间有一条无向边\(1\le v,u\le n\)。 保证没有重边和自环。

 

输出格式:

第一行一个正整数\(ns\),表示这个图中有\(ns\)个结点可选。

 

接下来一行,共\(ns\)个整数,每个整数表示一个可选结点的编号。**请按编号从小到大的顺序输出。**

数据保证图中至少存在一个可选的结点。

 

输入输出样例

输入样例#1:
6 6
1 2
1 3
2 4
2 5
4 6
5 6
输出样例#1:
3
4 5 6

说明

对于\(40\)%的数据,\(n,m\le 1,000,\)

 

另存在\(10\)%的数据,\(m=n-1,\)

 

另存在\(20\)%的数据,\(m=n,\)

 

对于\(100\)%的数据,\(n,m\le 100,000.\)

 

命题人:\(\mathrm{Jasonvictoryan}\)

题解:

   对于40%的数据来说,\(O(n^2)\)是可以过的。枚举每个点作为题意要求点时,原图是否为一棵树。

 

   那么另外30%的数据分别为”n=m”/”n=m+1″,一眼看上去,好像分别是一个环和一棵树。不过这两种情况并不全面,为什么呢?如果n=m+1,当有点孤立出来时,图不再连通,点所不在的连通块就可能不是一棵树;而同时,当n=m时,可能是环的变种,像下图这样,一棵树中两个没有直接相连的点被连上一条边,也会成环,这只是最特殊的情况。因此30分也不好得。

   重新回到题面上来,题目让我们把给出的图删掉一个点后变成一棵树。对于这个图,我们所了解的是它的n个点,m条边。而目标树则是确定的,因为删掉一个点后,它一定会剩下n-1个点,n-2条边。因此我们对于原图上的每个点,删掉它会移除图中的与它的度个数相同条边。而我们要把m变为n-2,并且只删除一个点,那么我们就要删掉一个度为m-(n-2)的点。

 

   树是一棵无向连通图,为了保证图的连通性,删去的这个点不能是图的割点,因此tarjan预处理一下,就知道哪个点是割点,哪个点不是。最后再枚举点,判断度数是否合法就可以了(度数在读边时处理出来)。

 

Code:

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::min;
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[201000];
int head[101000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int d[101000];
int dfn[101000],low[101000],cnt=0;
int cut[101000];//是否为割点
void tarjan(int x,int from)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            if(dfn[e[i].n])
                low[x]=min(low[x],dfn[e[i].n]);
            else
            {
                tarjan(e[i].n,x);
                low[x]=min(low[x],low[e[i].n]);
            }
            if(low[e[i].n]>dfn[x])
                cut[x]=1;
        }
}
int ans[101000];
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        d[u]++;//度+1
        d[v]++;
    }
    tarjan(1,1);
    cnt=0;
    for(int i=1;i<=n;i++)
        if(!cut[i]&&d[i]==m-(n-2))
            ans[++cnt]=i;
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d ",ans[i]);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */