I_LOVE_XYN @ 2024-06-13 20:44:33
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define int long long
using namespace std;
inline int read(){
char x = getchar();
int l = 1,d = 0;
while(!isdigit(x)) l = (x == '-' ? -l : l),x = getchar();
while(isdigit(x)) d = (d << 1) + (d << 3) + x - 48,x = getchar();
return l * d;
}
inline void write(int x){
int cnt = 0,p[106];
if(x < 0) putchar('-'),x = -x;
if(!x) putchar('0');
while(x){
p[++cnt] = x % 10;
x /= 10;
}
for(int i = cnt;i >= 1; i--) putchar(p[i] + '0');
}
const int N = 100000;
int n,m,tar,cnt,dfn[N],low[N],p[N],vis[N];
vector<int> edge[N],team[N];
stack<int> st;
void dfs(int x){
st.push(x);
dfn[x] = low[x] = ++cnt;
for(auto &to : edge[x])
if(!dfn[to]){
dfs(to);
low[x] = min(low[x],low[to]);
}else if(!p[to])
low[x] = min(low[x],dfn[to]);
if(low[x] == dfn[x]){
int head;
tar++;
do{
head = st.top();
st.pop();
p[head] = tar;
team[tar].push_back(head);
}while(head != x);
}
}
signed main(){
n = read(),m = read();
for(int i = 1;i <= n; i++) edge[read()].push_back(read());
for(int i = 1;i <= n; i++)
if(!dfn[i])
dfs(i);
write(tar),putchar('\n');
for(int i = 1;i <= tar; i++) sort(team[i].begin(),team[i].end());
for(int i = 1;i <= n; i++){
if(vis[p[i]]) continue;
vis[p[i]] = 1;
for(auto &to : team[p[i]])
write(to),putchar(' ');
putchar('\n');
}
return 0;
}
by Lu_xZ @ 2024-06-13 20:54:57
进栈时 p 没连带更新
by Lu_xZ @ 2024-06-13 21:03:22
@I_LOVE_XYN 看错了。
你边数写的是 n
by I_LOVE_XYN @ 2024-06-13 21:24:15
@Lu_xZ 感谢dalao,我这错误真是离谱
by I_LOVE_XYN @ 2024-06-13 21:25:03
@Lu_xZ A了,感谢