算法复习——割点（洛谷3388）

题目：

题目背景

割点

题目描述

给出一个n个点，m条边的无向图，求图的割点。

输入输出格式

输入格式：

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式：

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1：

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

输出样例#1：

1 
5

说明

n,m均为100000

tarjan 图不一定联通！！！

题解：

  洛谷的输出样例有误····md半天才看出来

  另外注意叶节点不是割点！！！！！

  还有就是原图不一定联通····

  幸好打了这个板···不然遇到割点题就惨了

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=100001;
int fst[N],nxt[N*2],go[N*2],tot=0;
int n,m,low[N],dfn[N],cnt=0,father[N];
bool jud[N];
inline void comb(int a,int b)
{
  nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;
  nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a;
}
inline void dfs(int u)
{
  low[u]=dfn[u]=++cnt;
  int child=0;
  for(int e=fst[u];e;e=nxt[e])
  {
    int v=go[e];
    if(!dfn[v])
    {
      father[v]=father[u];
      dfs(v);
      low[u]=min(low[u],low[v]);
      if(low[v]>=dfn[u]&&father[u]!=u)  jud[u]=true;
      if(father[u]==u)  child++;
    }
    else  low[u]=min(low[u],dfn[v]);
  }
  if(father[u]==u&&child>=2)  jud[u]=true;
}
int main()
{
  //freopen("a.in","r",stdin);
  scanf("%d%d",&n,&m);
  int a,b;
  for(int i=1;i<=n;i++)
    father[i]=i;
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&a,&b);
    comb(a,b);
  }
  for(int i=1;i<=n;i++)
    if(!dfn[i]) 
      dfs(i);
  int ans=0;
  for(int i=1;i<=n;i++)
    if(jud[i])
      ans++;
  cout<<ans<<endl;
  for(int i=1;i<=n;i++)
    if(jud[i])
      cout<<i<<" ";
  return 0;
}