【圖論——割點與橋】——洛谷P3388【模闆】割點（割頂）

此處用u表示這個節點，用v表示u的子節點，fa表示u的父親節點

pre[u]表示dfs中u這個點被第幾個掃到

用low[u]表示u能到的v中pre[v]的最小值

割點：如果low[v]<=pre[u]就證明u這個點的子節點沒有辦法到達u的父親節點也就證明去掉這個點就會産生一個連通分量（多一個不相連的圖）

利用這個性質就可以求割點

橋：方法與割點相同判斷時不同low[v]<pre[u],少了一個等于号。這是因為我們的圖中如果v這個節點可以連接配接到u這個節點那麼即使去除u到v這條邊與無法多産生一個連通分量

判斷時要保證其不沿着原路傳回

dfs就是将u的所有邊走一遍

pre[v]==0 走上述操作

pre[v]!=0 判斷如果是之前掃過的點為了保證low[u]最小讓lo[u]=pre[v];

最後還要加一個特判

如果這是第一個點且隻有一個直接相連的子節點那麼即使去了這個點也沒有多産生連通分量，是以我們不将它判定為割點。

//此處程式為xoj.red上的題目，是既求割點又求橋的

#include<cstdio>

#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
vector <int> g[100001];
vector <int> clearg[100001];
int low[100001];
int pre[100001];
bool cut[100001];
int ctz=0;
int ansq=0;
int dfs(int u,int fa)
{
int lowu=++ctz;
pre[u]=ctz;
int child=0;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(pre[v]==0)
{
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u])
{
if(lowv>pre[u])
{
ansq++;
}
cut[u]=1;
}
}
else
{
if(pre[v]<pre[u]&&v!=fa)
{
lowu=min(lowu,pre[v]);
}
}
}
if(fa==0&&child==1)
{
cut[u]=0;
}
low[u]=lowu;
return lowu;
}
int main()
{
memset(low,0,sizeof(low));
memset(pre,0,sizeof(pre));
memset(cut,0,sizeof(cut));
while(1)
{
memset(low,0,sizeof(low));
memset(pre,0,sizeof(pre));
memset(cut,0,sizeof(cut));
ansq=0;
for(int i=1;i<=100001;i++)
{
g[i]=clearg[i];
}
scanf("%d %d",&n,&m);
if(n==0&&m==0)
{
return 0;
}
for(int i=1;i<=m;i++)
{
int x,y,w;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(pre[i]==0)
{
dfs(i,0);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(cut[i]==1)
{
ans++;
}
}
printf("%d %d\n",ans,ansq);
for(int i=1;i<=n;i++)
{
if(cut[i]==1)
{
printf("%d\n",i);
}
}
}
return 0;
}