__dragon_ @ 2024-11-14 18:45:49
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 10000;
struct edge{
int v,nxt;
}e[maxn * 20];
int n,m;
int head[maxn],idx;
int low[maxn],dfn[maxn],cnt;
int bel[maxn];
bool vis[maxn];
int sc;
vector<int>scc[maxn];
stack<int>st;
void adde(int u,int v)
{
++idx;
e[idx].v = v;
e[idx].nxt = head[u];
head[u] = idx;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++cnt;
vis[u] = 1;
st.push(u);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if (vis[v])
low[u] = min(low[u],dfn[v]);
}
if (low[u] == dfn[u])
{
sc ++;
while (st.top() != u)
{
scc[sc].push_back(st.top());
bel[st.top()] = sc;
vis[st.top()] = 0;
st.pop();
}
scc[sc].push_back(u);
bel[u] = sc;
vis[u] = 0;
st.pop();
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
while (m--)
{
int u,v;
scanf("%lld%lld",&u,&v);
if(u == v)
continue;
adde(u,v);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
printf("%lld\n",sc);
for (int i = 1; i <= sc; i++)
sort(scc[i].begin(),scc[i].end());
bool b[maxn] = {};
for (int i = 1; i <= n; i++)
{
if (!b[bel[i]])
{
for (auto j : scc[bel[i]])
printf("%lld ",j);
putchar('\n');
b[bel[i]] = 1;
}
}
return 0;
}
by __dragon_ @ 2024-11-14 18:49:32
死因:数组没开够
此贴结