WA 求助
查看原帖
WA 求助
1287433
ycyxh1楼主2024/11/21 19:43

#4 #6 #11 #13 #14 #15 #16 #17 #18 #21 #22 WA 求助

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>a[500001];
struct qwq{
    set<int>s;
}Ans[500001];
struct Node{
	ll dfn,low,sum;
}nod[500001];
ll idx=0,ans=0;
stack<ll>q;
bool cmp(qwq x1,qwq x2){
    return *x1.s.begin()<*x2.s.begin();
}
void tarjan(ll i){
	nod[i].low=nod[i].dfn=++idx;
	q.push(i);
	if(nod[i].sum==0){
		Ans[++ans].s.insert(i);
        if(Ans[ans].s.size()==1){
            Ans[ans].s.clear();
            --ans;
        }
	}
	for(auto it:a[i]){
		if(!nod[it].dfn){
			tarjan(it);
			nod[i].low=min(nod[i].low,nod[it].low);
			if(nod[it].low>=nod[i].dfn){
				ans++;
				ll x;
				while(x!=it){
					x=q.top();
					Ans[ans].s.insert(x);
					q.pop();
				}
				Ans[ans].s.insert(i);
                if(Ans[ans].s.size()==1){
                    Ans[ans].s.clear();
                    --ans;
                }
			}
		}
		else{
			nod[i].low=min(nod[i].low,nod[it].dfn);
		}
	}
}
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		ll u,v;
		scanf("%lld%lld",&u,&v);
		if(u!=v){
			nod[u].sum++;
			nod[v].sum++;
			a[u].push_back(v);
			a[v].push_back(u);
		}
	}
	for(int i=1;i<=n;i++){
		if(nod[i].dfn==0){
			tarjan(i);
		}
	}
	printf("%lld\n",ans);
    sort(Ans+1,Ans+ans+1,cmp);
	for(int i=1;i<=ans;i++){
		for(auto it:Ans[i].s){
            cout<<it<<' ';
        }
        cout<<'\n';
	}
	return 0;
}
2024/11/21 19:43
加载中...