[luogu3388][割点]

题目链接

思路

真板子题。割点是指在一个无向图中,删去之后图将不再连通的点。可以用tarjan算法求。根据割点有两种情况,一种是根,一种是非根。如果不是根的就去判断在tarjan的时候当前节点所能到的最靠上的点。如果最靠上的点在当前点的下面,那么当前点就是割点,否则不是。对于是根的点。只要判断是不是可以从儿子中搜两遍就可以了。

代码

#include<cstdio>
#include<iostream>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
const int N = 20000 + 100,M = 100000+100;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node {
    int v,nxt;
}e[M * 2];
int ejs,head[N],dfn[N],low[N],ans[N];
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u]; head[u] = ejs;
}
int now;
int js;
int rd;
void tarjan(int u) {
    int rd = 0;
    low[u] = dfn[u] = ++js;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            if(u == now)
            rd++;
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u] && u != now) ans[u] = 1;//!!! 
        }
        else low[u] = min(low[u],dfn[v]);
    }
    if(rd >= 2 && u == now ) ans[u] = 1;
    return;
}
int main() {
    int n = read(), m = read();
    for(int i = 1;i <= m;++i) {
        int u = read(), v = read();
        add(u,v); add(v,u);
    }
    for(int i = 1;i <= n;++i) {
        if(!dfn[i]) {
            now = i;
            tarjan(i);
        }
    }
    int tot = 0;
    for(int i =1; i <= n;++i)
        if(ans[i]) tot++;
    printf("%d\n",tot);
    for(int i = 1; i <= n;++i) 
        if(ans[i]) printf("%d ",i);
    return 0;
}

一言

心上有个人,才能活下去。 ——病相笔记

全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务