求调,悬赏
查看原帖
求调,悬赏
398818
Candycar楼主2023/4/30 14:41
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define rand RAND
#define LOCAL
using namespace std;
template<class Typ> Typ &re(Typ &x){char ch=getchar(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=getchar()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e5+5;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int dfn[maxn],low[maxn];
int n,m;
struct node{
    int to,nxt;
}E[maxn*4];
int head[maxn],cnt=1;
bool f[maxn];
void add(int u,int v){
    E[++cnt]={v,head[u]};
    head[u]=cnt;
}
int tot=0,flag=0,root;
void Tarjan(int u){
    dfn[u]=low[u]=++tot;
    flag=0;
    for(int i=head[u];i;i=E[i].nxt){
        int v=E[i].to;
        // cout<<u<<" "<<v<<endl;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                flag++;
                if(u!=root||flag>1)f[u]=1;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
signed main(){
    re(n),re(m);
    for(int i=1;i<=m;i++){
        int u,v;
        re(u),re(v);
        if(u==v)continue;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])root=i,Tarjan(i);
    }
    // cout<<114514<<endl;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f[i])ans++;
    }
    wt(ans),pt('\n');
    for(int i=1;i<=n;i++)if(f[i])wt(i),pt(' ');
    return 0;
}

32分求调,悬赏关注

2023/4/30 14:41
加载中...