#include<algorithm>
#include<cstdio>
#include<vector>
#define maxn 20000
#define maxm 120
using namespace std;
vector<int> e[maxn];
int gd[maxm];
int dfn[maxm],low[maxm];
int n,root,dtime,ans;
void tarjan(int u){
int i,v,tot=0;
low[u]=dfn[u]=++dtime;
for(i=0;i<e[u].size();i++){
v=e[u][i];
if(!dfn[v]){
tarjan(v);
++tot;
low[u]=min(low[v],low[u]);
if((u==root&&tot>1)||(u!=root&&low[v]>=dfn[u]))
if(!gd[u]) gd[u]=true,ans++;
}
else low[u]=min(low[u],dfn[v]);
}
return ;
}
int main(){
scanf("%d",&n);
int i,j,a,b,u,v;
while(scanf("%d%d",&u,&v)!=EOF){
e[u].push_back(v);
e[v].push_back(u);
}
for(i=1;i<=n;i++){
if(!dfn[i]){
root=i;
tarjan(i);
}
}
printf("%d
",ans);
for(i=1;i<=n;i++){
if(gd[i])
printf("%d
",i);
}
return 0;
}
割点
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define maxn 155
#define maxm 5005
using namespace std;
vector<int> vec[maxn];
bool bridge[maxn],vis[maxn];
int low[maxn],dfn[maxn];
int head[maxn],pre[maxn],ip,sol,tot;
int n,m,u,v,dtime;
struct node{
int v,next,use;
}edge[maxm<<2];
struct Bridge{
int u,v;
}bri[maxm];
bool cmp(Bridge x,Bridge y){
if(x.u!=y.u)
return x.u<y.u;
else
return x.v<y.v;
}
void tarjan(int u){
vis[u]=1;
dfn[u]=low[u]=dtime++;
for(int i=head[u];i!=-1;i=edge[i].next){
if(!edge[i].use){
edge[i].use=edge[i^1].use=1;
int v=edge[i].v;
if(!vis[v]){
pre[v]=u;
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
sol++;
bridge[v]=1;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
edge[ip].v=v;
edge[ip].use=0;
edge[ip].next=head[u];
head[u]=ip++;
edge[ip].v=u;
edge[ip].use=0;
edge[ip].next=head[v];
head[v]=ip++;
}
pre[1]=1;
tarjan(1);
for(int i=1;i<=n;i++){
if(bridge[i]){
tot++;
if(pre[i]>i){
bri[tot].u=i;
bri[tot].v=pre[i];
}
else{
bri[tot].u=pre[i];
bri[tot].v=i;
}
}
}
sort(bri+1,bri+tot+1,cmp);
for(int i=1;i<=tot;i++)
printf("%d %d
",bri[i].u,bri[i].v);
return 0;
}