题解回家

## Description  
x教授是位德高望重的教授 , 他的课以受学生欢迎而著称 .  
然而 , 有这么一个熊孩子 , 他上谁的课都不听 , x教授也不例外 . 最让人不能忍受的是 , 他有时还会在上最后一节课时偷偷溜走 , 提前回家 .  
有一次 , x教授的课在最后一节 , 然而这并不妨碍熊孩子偷偷回家 . 不巧的是 , 他刚出校 , 正讲得酣畅淋漓的x教授往他的座位瞟了一眼 , 立马发现了不对 . x教授顿时就火冒三丈,立即派出他的课代表llg去把这个熊孩子给捉回来 , 他要好好教育这个熊孩子一番 .  
熊孩子回家途中的建筑有 $n$ 个 , 其中 $1$ 号建筑为学校 , $n$ 号建筑为熊孩子的家 . 有些建筑之间有公路相连 , 注意公路是双向的 . llg早已仔细研究过这些东西 , 他发现如果他在一些建筑的位置等着 , 一定可以等到回家的熊孩子 ( 假设课代表可以先于熊孩子到达任意一个建筑 ) . 但由于某种原因 , llg不愿意在熊孩子的家里等他 . 当然 , 由于熊孩子已经出了学校 , 学校也行不通 .   
所以 , 现在llg又一个问题难住了 : 有多少个这样熊孩子回家必经的地方呢 ?  
## Solution  
先用 $tarjan$ 求出每个节点的 $dfn,low$ , 然后在搜索树上由 $n$ 号结点向 $1$ 号节点跳父亲 , 并判断当前点的父亲对于这个点来说是不是割点 .   
```cpp
dfn[fa[now]]<=low[now]
```
也许可以算是 $tarjan$ 的扩展用法 .  
## Code  
```cpp

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=2e5+5;
const int maxm=4e5+5;
int T;
int ans[maxn],ansnum;
class graph
{
    public:
    int n,m;
    int head[maxn],ver[maxm<<1],nxt[maxm<<1];
    int tot=1;
    void add(int x,int y)
    {
        ver[++tot]=y;nxt[tot]=head[x];
        head[x]=tot;
    }
    void link(int x,int y){add(x,y);add(y,x);}
    int dfn[maxn],eu[maxn],low[maxn],tim;
    void clear()
    {
        for(int i=1;i<=n;i++)head[i]=dfn[i]=0;
        for(int i=2;i<=m*2+2;i++)nxt[i]=0;
        tot=1;
        tim=0;
        ansnum=0;
    }
    int fa[maxn];
    void tarjan(int x,int last)
    {
        dfn[x]=low[x]=++tim;eu[dfn[x]]=x;
        for(int i=head[x];i;i=nxt[i])
        {
            if(!dfn[ver[i]])
            {
                fa[ver[i]]=x;
                tarjan(ver[i],i);
                low[x]=min(low[x],low[ver[i]]);
            }
            else if(ver[i]!=last)low[x]=min(low[x],dfn[ver[i]]);
        }
    }
}o;
int main()
{
    T=read();
    while(T--)
    {
        o.n=read();o.m=read();
        o.clear();
        for(int i=1;i<=o.m;i++)
        {
            int u,v;u=read();v=read();
            if(u==v)continue;
            o.link(u,v);
        }
        o.tarjan(1,0);
        if(!o.dfn[o.n])
        {
            printf("0\n\n");
            continue;
        }
        else 
        {
            int now=o.n;
            while(now!=1)
            {
                if(o.dfn[o.fa[now]]<=o.low[now]&&o.fa[now]!=1)ans[++ansnum]=o.fa[now];
                now=o.fa[now];
            }
            sort(ans+1,ans+ansnum+1);
            printf("%d\n",ansnum);
            for(int i=1;i<=ansnum;i++)printf("%d ",ans[i]);printf("\n");
        }
    }
    return 0;
}

```

正在渲染内容...

题解 回家