DreamTsinghua @ 2023-11-13 07:35:03
#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
``
by lyxleo @ 2023-11-13 07:38:01
评测机炸了,UKE
by DreamTsinghua @ 2023-11-13 09:12:31
@lyxleo 蟹蟹