洛谷3388-割点-C++ && python-(tarjan割点算法)

AC代码

C++

#include<iostream>
#include<vector>
using namespace std;

#define N 20010
int n,m;
int dfn[N],low[N],vis[N],tim=1;
int flag[N],u,v;
vector<int> point[N];
int min(int x,int y){
          
   
	return x>y?y:x;
}
void tarjan(int cur,int far){
          
   
	dfn[cur]=tim;
	low[cur]=tim++;
	int child=0;
	for(int i=0;i<point[cur].size();i++){
          
   
		int v=point[cur][i];
		if(!vis[v]){
          
   
			vis[v]=1;
			child++;
			
			tarjan(v,cur);
			low[cur]=min(low[cur],low[v]);
			if(cur!=far && low[v]>=dfn[cur])
				flag[cur]=1;
			if(cur==far and child>=2)
				flag[cur]=1;
		}
		else if(v!=far){
          
   
			low[cur]=min(low[cur],dfn[v]);
		}
	}
}
int main(){
          
   
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
          
   
		scanf("%d%d",&u,&v);
		point[u].push_back(v);
		point[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
          
   
		if(dfn[i]==0){
          
   
			vis[i]=1;
			tarjan(i,i);
		}
	}
	int tmp=0;
	for(int i=1;i<=n;i++){
          
   
		if(flag[i])
			tmp++;
	}
	printf("%d
",tmp);
	for(int i=1;i<=n;i++){
          
   
		if(flag[i])
			printf("%d ",i);
	}
	return 0;
}

Python

global n,m
global point
global dfn,low,vis,time
global flag
global root
def tarjan(cur,far):
    global time
    dfn[cur],low[cur]=time,time
    time+=1

    child=0
    for i in range(len(point[cur])):
        v=point[cur][i]
        if not vis[v]:
            vis[v]=1
            child+=1
            
            tarjan(v,cur)
            low[cur]=min(low[cur],low[v])

            if cur!=far and low[v]>=dfn[cur]:
                flag[cur]=1
            if cur==far and child>=2:
                flag[cur]=1
        elif v!=far:
            low[cur]=min(low[cur],dfn[v])
n,m=map(int,input().split())
point=[[] for _ in range(n+1)]
for i in range(m):
    x,y=map(int,input().split())
    point[x].append(y)
    point[y].append(x)
dfn=[0 for _ in range(n+1)]
low=[0 for _ in range(n+1)]
vis=[0 for _ in range(n+1)]

flag=[0 for _ in range(n+1)]
time=1
for i in range(1,n+1):
    if dfn[i]==0:
        vis[i]=1
        tarjan(i,i)
print(sum(flag))
for i in range(1,n+1):
    if flag[i]:
        print(i,end=" ")