Edge cutting template (linked list)

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;
}

Keywords: less

Added by kippi on Tue, 12 Nov 2019 22:23:36 +0200