点双玄关求调
查看原帖
点双玄关求调
1287451
MuktorFM楼主2025/7/24 17:06

错误数据:

3.in

5 5
2 5
5 5
5 5
4 1
3 5

3.out

3
2 1 4
2 2 5
2 3 5
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,idx,ans,dfn[500005],low[500005],hd[500005];
vector<int> ve[500005];
stack<int> st;
vector<int> bcc[500005];
bool cmp(int a,int b){return a > b;}
void tarjan(int now,int root){
	dfn[now] = low[now] = ++idx;
	if(now == root && !hd[now]) bcc[++ans].push_back(now);
	st.push(now);
	for(auto i : ve[now]){
		if(!dfn[i]){
			tarjan(i,root);
			low[now] = min(low[now],low[i]);
			if(low[i] >= dfn[now]){
				ans++;
				int p;
				do{
					p = st.top();
					st.pop();
					bcc[ans].push_back(p);
				}while(p != i);
				bcc[ans].push_back(now);
			}
		}else low[now] = min(low[now],dfn[i]);
	}
}
signed main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int u,v; cin >> u >> v;
		if(u == v) continue;
		ve[u].push_back(v);
        hd[u] = k++;
		ve[v].push_back(u);
        hd[v] = k++;
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i]) tarjan(i,i);
	}
	cout << ans << "\n";
	for(int i = 1;i <= ans;i++){
		cout << bcc[i].size() << " ";
		for(auto j : bcc[i]) cout << j << " ";
		cout << "\n";
	}
    return 0;
}
2025/7/24 17:06
加载中...