The title comes from Luogu
Background of topic
Cut point
Title Description
In this paper, we give an undirected graph with nn points and mm edges, and find the cut points of the graph.
I / O format
Input format:
Input n,mn,m in the first line
In the following mm lines, input x,yx,y for each line to indicate that there is an edge between xx and yy
Output format:
Number of output cut points in the first line
The second line outputs nodes from small to large according to the node number, separated by spaces
Example of input and output
Input example ා 1:
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
Output example:
1
5
Explain
For all data, n \le 20000n ≤ 20000, m \le 100000m ≤ 100000
The number of points is greater than 00 and less than or equal to nn.
tarjan graphs are not necessarily connected. (pay special attention to this place. It's trapped ~ ~)
Code adapted from AHA algorithm
#include<bits/stdc++.h> using namespace std; struct node{ int v;//u->v int naxt; }a[200005];int head[20005];//Array linked list int c; void addage(int x,int y) { a[++c].v =y;a[c].naxt =head[x];head[x]=c; a[++c].v =x;a[c].naxt =head[y];head[y]=c; return;//Undirected graph } int n,m,indexx,root,countt;int low[20005],num[20005],flag[20005]; void dfs( int cur, int father ) { int child=0,j; indexx++; num[cur]=indexx; low[cur]=indexx; for(j=head[cur];j!=-1;j=a[j].naxt ){ if(num[a[j].v ]==0) { child++; dfs(a[j].v ,cur); low[cur]=min(low[cur],low[a[j].v ]); if(cur!=root&&low[a[j].v ]>=num[cur]) { flag[cur]=1; } if(cur==root&&child>=2) { flag[cur]=1; } } else if(a[j].v !=father) low[cur]=min(low[cur],num[a[j].v ]); } return; } int main(void) { int i,x,y; scanf("%d %d",&n,&m); c=0;indexx=0;countt=0; memset(head,-1,sizeof(head));//Initialization of linked list memset(flag,0,sizeof(flag)); memset(num,0,sizeof(num)); for(i=1;i<=m;i++){ scanf("%d %d",&x,&y); addage(x,y); } root=1; for(i=1;i<=n;i++) if(num[i]==0) { root=i;//Because the graph is not connected, the root of the graph will change with each time dfs(i,root);//Because the picture in the question is not necessarily connected }//It's been A long time. It's just stuck here for(i=1;i<=n;i++) if(flag[i]) countt++; printf("%d\n",countt); for(i=1;i<=n;i++) if(flag[i]) printf("%d ",i); //printf("\n"); return 0; }