洛谷 P3388 【模闆】割點（tarjan割點+求橋模闆）

題目背景

割點

題目描述

給出一個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≤20000

m≤100000

點的編号均大于000小于等于nnn。

tarjan圖不一定聯通。

（模闆，詳情看注釋，注釋代碼部分為求橋的寫法）

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e4+10;
vector <int> ve[maxn];
int cut[maxn],dfn[maxn],cnt,ans[maxn];
vector<pair<int,int> > bridge; 
int tarjan(int u,int fa)
{
	//記錄有幾個孩子，根節點有至少兩個孩子才算割點。 
	int child=0;
	int lowu=dfn[u]=++cnt;
	for(int i=0;i<ve[u].size();i++)
	{
		int v=ve[u][i];
		if(!dfn[v])
		{
			child++;
			//求孩子v子樹上的最小的low 
			int lowv=tarjan(v,u); 
			lowu=min(lowu,lowv);
			//如果lowv>dfn[u]，說明v沒有指向u祖先的點，說明u是割點 
			if(lowv>=dfn[u])
			{
			  cut[u]=1; 
//			  int from=u,to=v;
//			  if(from>to)
//			    swap(from,to);
//			  bridge.push_back(make_pair(from,to));	
			}	
		}
		else if(v!=fa)
		{
			//求u子樹上的最小的low 
		    lowu=min(lowu,dfn[v]);	
		}
		
	}
	//根節點有至少兩個孩子才算割點
	if(fa==0&&child<=1)
	  cut[u]=0;
	return lowu;
	
}
int main(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
    	int u,v;
    	scanf("%d%d",&u,&v);
    	ve[u].push_back(v);
    	ve[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		 tarjan(i,0);			  
	}
	int c=0;
	for(int i=1;i<=n;i++)
	   if(cut[i]) ans[c++]=i;
	printf("%d\n",c);
	for(int i=0;i<c;i++)
	  printf("%d%c",ans[i],i==c-1?'\n':' ');
//	for(int i=0;i<bridge.size();i++)
//	  printf("%d %d\n",bridge[i].first,bridge[i].second);
	
	return 0;
}