题目背景
割点
题目描述
给出一个n个点,m条边的无向图,求图的割点。
输入输出格式
输入格式:
第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式:
第一行输出割点个数
第二行按照节点编号从小到大输出节点,用空格隔开
输入输出样例
输入样例#1:
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
输出样例#1:
1 5
说明
n,m均为100000
tarjan 图不一定联通!!!
一个割点模板,就是要注意if(dfn[i])的括号的位置
#include<cstdio> #include<cstring> #include<queue> #define min(a,b) (a>b?b:a) using namespace std; const int maxm = 1e5 + 100; const int maxn = 1e5 + 100; struct edge{ int v, next; }e[maxm * 2]; int cnt, n, m, clock = 0, root, flag = 0, anscnt = 0; int head[maxn]; int dfn[maxn], low[maxn]; void adde(const int &u, const int &v) { e[cnt] = (edge) {v, head[u]}; head[u] = cnt++; } priority_queue<int, vector<int >, greater<int> > ans; int tarjan(int u, int fa) { dfn[u] = low[u] = ++clock; int num = 0; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if(v == fa) continue; if(dfn[v]) low[u] = min(low[u], low[v]); else { low[u] = min(low[u], tarjan(v, u)); if(low[v] >= dfn[u]) num++; } } if(num >= 1 && u != root) ans.push(u), ++anscnt; if(num >= 2 && u == root) ans.push(u), ++anscnt; return low[u]; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); adde(u, v); adde(v, u); } for(int i = 1; i <= n; i++) if(!dfn[i]){ root = i; tarjan(i, 0); } printf("%d\n", anscnt); while(!ans.empty()) { printf("%d ",ans.top()); ans.pop(); } return 0; }
没有帐号? 立即注册