题目背景
割点
题目描述
给出一个n个点，m条边的无向图，求图的割点。
输入输出格式
输入格式：
第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式：
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入输出样例
输入样例#1：
6 71 21 31 42 53 54 55 6
输出样例#1：
1 5
说明
n,m均为100000
tarjan 图不一定联通！！！
割点真是一个非常神奇的东西。
虽然和tarjan很像，
而且能理解其中的奥秘。
但是代码还是看的一脸蒙蔽，。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define lli long long int 9 using namespace std;10 const int MAXN=1000001;11 const int maxn=0x7fffff;12 inline void read(int &n)13 {14 char c='+';int x=0;bool flag=0;15 while(c<'0'||c>'9')16 {c=getchar();if(c=='-')flag=1;}17 while(c>='0'&&c<='9')18 {x=(x<<1)+(x<<3)+c-48;c=getchar();}19 flag==1?n=-x:n=x;20 }21 int n,m;22 struct node23 {24 int u,v,nxt;25 }edge[MAXN];26 int head[MAXN];27 int num=1;28 void add_edge(int x,int y)29 {30 edge[num].u=x;31 edge[num].v=y;32 edge[num].nxt=head[x];33 head[x]=num++;34 }35 int dfn[MAXN];//dfs的顺序36 int low[MAXN];// 每个点能追溯到的最近公共祖先37 int vis[MAXN];38 int ans[MAXN];// 是否是割点 39 int ansnum; //割点的数量 40 int tot=0;41 int tarjan(int now,int fa)42 {43 dfn[now]=low[now]=++tot; 44 int ch=0;45 for(int i=head[now];i!=-1;i=edge[i].nxt)46 {47 if(low[edge[i].v]!=0)48 low[edge[i].u]=min(low[edge[i].u],dfn[edge[i].v]);49 else 50 if(low[edge[i].v]==0)51 {52 ch++;//孩子的数量53 int nxt=tarjan(edge[i].v,edge[i].u);54 low[edge[i].u]=min(low[edge[i].u],low[edge[i].v]);55 if((fa==-1&&ch>1)||(fa!=-1&&dfn[edge[i].u]==low[edge[i].v]))56 {57 if(!ans[edge[i].u])58 {59 ans[edge[i].u]=1;60 ansnum++;61 }62 }63 }64 }65 return low[now];66 }67 int main()68 {69 read(n);read(m);70 memset(head,-1,sizeof(head));71 for(int i=1;i<=m;i++)72 {73 int x,y;74 read(x);read(y);75 add_edge(x,y);76 add_edge(y,x);77 }78 for(int i=1;i<=n;i++)79 if(low[i]==0)80 tarjan(i,-1); 81 printf("%d\n",ansnum);82 for(int i=1;i<=n;i++)83 if(ans[i]==1)84 printf("%d ",i);85 return 0;86 }
update in 2017.11.7
补一份利用void类型实现的代码
#include#include #include #include #include using namespace std;const int MAXN=1e6+10;inline int read(){ char c=getchar();int f=1,x=0; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;}struct node{ int u,v,nxt;}edge[MAXN];int head[MAXN];int num=1;inline void add_edge(int x,int y){ edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++;}int dfn[MAXN];//询问的时间 int low[MAXN];//最早能追溯到的祖先 int n,m,tot;//当前已经枚举了多少节点 int ans[MAXN];//是否是割点 int ansnum=0; void tarjan(int now,int fa){ dfn[now]=low[now]=++tot; int ch=0; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(low[edge[i].v]!=0) low[now]=min(low[now],dfn[edge[i].v]); else if(low[edge[i].v]==0) { ch++; tarjan(edge[i].v,now); low[now]=min(low[now],low[edge[i].v]); if((fa==-1&&ch>1)||(fa!=-1&&(dfn[now]==low[edge[i].v]) ) ) //一个点是根节点&&孩子的数量>1 //或是这个点不是根节点且访问的点的祖先是它 if(ans[edge[i].u]==0) ans[edge[i].u]=1,ansnum++; } }}int main(){ memset(head,-1,sizeof(head)); n=read();m=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1); printf("%d\n",ansnum); for(int i=1;i<=n;i++) if(ans[i]) printf("%d ",i); return 0;}