只有输出顺序不同,为什么0pt? 不是任意顺序都行吗
查看原帖
只有输出顺序不同,为什么0pt? 不是任意顺序都行吗
1037516
DreamTsinghua楼主2023/11/13 07:35
#include <bits/stdc++.h>

using namespace std ;

const int N = 4e6 + 10 ;

int n, m ;
int e[N], ne[N], h[N], idx ;
int dfs[N], low[N], id[N], dcc_cnt ;
bool st[N] ;
int din[N] ;
//vector <vector<int>> ans ;
vector <int> ans[N] ;

int ti ;
stack <int> s ;

void add(int a, int b) {
	e[idx] = b ;
	ne[idx] = h[a] ;
	h[a] = idx ++ ;
}

void tarjan(int u, int from) {
	dfs[u] = low[u] = ++ ti ;
	s.push(u) ;

	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i] ;
		if (!dfs[j]) {
			tarjan(j, i) ;
			low[u] = min(low[u], low[j]) ;
			if (dfs[u] < low[j])
				st[i] = st[i ^ 1] =  1 ;
		} else if (i != (from ^ 1))
			low[u] = min(low[u], dfs[j]) ;
	}

	if (dfs[u] == low[u]) {
		int y ;
		++ dcc_cnt ;
		do {
			y = s.top() ;
			s.pop() ;
			id[y] = dcc_cnt ;
		} while (u != y) ;
	}
}

int main() {
	cin >> n >> m ;

	memset(h, -1, sizeof h) ;
	for (int i = 1;  i <= m ; i ++) {
		int a, b ;
		cin >> a >> b ;
		if (a == b)
			continue ;

		add(a, b) ;
		add(b, a) ;
	}

	for (int i = 1 ; i <= n ; i ++)
		if (dfs[i] == 0)
			tarjan(i, -1) ;

	cout << dcc_cnt << endl ;



	for (int i = 1 ; i <= n ; i ++) {
		ans[id[i]].push_back(i) ;
	}
	for (int i = 1 ; i <= dcc_cnt ; i ++) {
		cout << ans[i].size() << ' ' ;
		for (auto t : ans[i])
			cout << t << ' ' ;
		cout << endl ;
	}
	return 0 ;
}

样例1:
4 3
1 2
4 2
2 2

程序输出:
4
1 4
1 2
1 1
1 3
答案输出:
4
1 1
1 2
1 3
1 4

什么原因啊qwq
``
2023/11/13 07:35
加载中...