P3388 【模板】割点(割顶)求助
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/3/5 16:48
  • 上次更新2023/10/28 07:13:46
查看原帖
P3388 【模板】割点(割顶)求助
439327
南瓜桐楼主2022/3/5 16:48
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
namespace wzl{
vector<int> head,to,nxt;
int m,n,num = 0;
int root;
const int maxn = 2e4 + 1;
const int maxm = 1e5 + 1;
int low[maxn]={},dfn[maxn]={},cut[maxn]={};
void add(int u,int v){
	to.push_back(v);
	nxt.push_back(head[u]);
	head[u] = nxt.size() - 1;
	return;
}
void tarjan(int x,int fa){
	dfn[x] = low[x] = ++num;
	int cnt = 0;
	for(int i = head[x]; i != -1; i = nxt[i]){
		int y = to[i];
		if(!dfn[y]){
			++cnt;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if((x == root && cnt > 1) || (x != root && dfn[x] <= low[y] && cnt >= 1 && y != fa)){
				cut[x] = 1;
			}
		}else{
			low[x] = min(low[x],dfn[y]);
		}
	}
	return;
}
void main(){
	cin>>n>>m;
	head.resize(n+1,-1);
	for(int i = 1;i <= m; ++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(root = 1; root <= n; ++root){
		if(dfn[root] == 0){
			tarjan(root,0);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i){
		if(cut[i] == 1){
			++ans;
		} 
	}
	
	cout<<ans<<endl;
	for(int i = 1; i <= n; ++i){
		if(cut[i] == 1){
			cout<<i<<' ';
		}
	}
	return;
}

}


int main(){
	wzl::main();
	return 0;
}
2022/3/5 16:48
加载中...