GODTREE @ 2024-03-24 11:41:13
re了
#include <bits/stdc++.h>
#define N 50005
using namespace std;
struct edge
{
int nxt,to;
}e[N],fe[N];
int n,m,head[N],cnt,s[N],fcnt,od[N],fhead[N];
vector<int> scc[N];
bool vis[N];
void add(int u,int v)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
}
void fadd(int u,int v)
{
fe[++fcnt].nxt=fhead[u];
fhead[u]=fcnt;
fe[fcnt].to=v;
}
void dfs1(int u)
{
vis[u]=1;
for (int i=head[u];i!=0;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]==0)
{
dfs1(v);
}
}
s[++cnt]=u;
}
void dfs2(int u)
{
vis[u]=1;
for (int i=fhead[u];i!=0;i=fe[i].nxt)
{
int v=fe[i].to;
if(vis[v]==0)
{
dfs2(v);
}
}
scc[cnt].push_back(u);
}
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
fadd(y,x);
}
cnt=0;
dfs1(1);
memset(vis,0,sizeof(vis));
cnt=0;
for (int i=n;i>=1;i--)
{
if (vis[s[i]]==0)
{
dfs2(s[i]);
od[s[i]]=cnt;
}
cnt++;
}
for (int i=1;i<=n;i++)
{
sort(scc[i].begin(),scc[i].end());
}
for (int i=1;i<=n;i++)
{
if(vis[i]==0)
{
for (int j=0;j<scc[i].size();j++)
{
cout<<scc[i][j]<<" ";
}
}
cout<<"\n";
}
return 0;
}
by __My0217__ @ 2024-03-24 12:18:20
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define N 10005
using namespace std;
vector<int> G[N];
vector<int> _G[N];
vector<int> ans[N];
int vis[N], h[N], tot, cnt, _vis[N];
void dfs1(int u){
vis[u] = 1;
for(int i = 0 ; i < G[u].size() ; i++){
int to = G[u][i];
if(vis[to]) continue;
dfs1(to);
}
h[++tot] = u;
}
void dfs2(int u, int k){
vis[u] = k;
ans[k].push_back(u);
for(int i = 0 ; i < _G[u].size() ; i++){
int to = _G[u][i];
if(vis[to]) continue;
dfs2(to, k);
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1 ; i <= m ; i++){
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
_G[v].push_back(u);
}
//puts("Ok");
for(int i = 1 ; i <= n ; i++){
if(vis[i]) continue;
dfs1(i);
}
//puts("Ok");
memset(vis, 0, sizeof(vis));
for(int i = tot ; i >= 1 ; i--){
if(vis[h[i]]) continue;
dfs2(h[i], ++cnt);
}
for(int i = 1 ; i <= cnt ; i++){
sort(ans[i].begin(), ans[i].end());
}
printf("%d\n", cnt);
for(int i = 1 ; i <= n ; i++){
int now = vis[i];
if(_vis[now]) continue;
_vis[now] = 1;
for(int j = 0 ; j < ans[now].size() ; j++){
printf("%d ", ans[now][j]);
} puts("");
}
return 0;
}