wusihao1931 @ 2022-10-07 22:02:57
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, M = 400010;
int n, m;
int id[N];
bool st[N];
int scc_cnt;
vector<int> ans[N];
stack<int> stk;
bool in_stk[N];
int h[N], e[M], ne[M], idx;
int low[N], dfn[N], timestamp;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx ++ ;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++ timestamp;
stk.push(u), in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
int y;
scc_cnt ++ ;
do
{
y = stk.top();
stk.pop();
in_stk[y] = false;
id[y] = scc_cnt;
ans[scc_cnt].push_back(y);
} while (y != u);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d %d", &a, &b);
add(a, b);
}
for (int i = 1; i <= n; i ++ )
if (!dfn[i])
tarjan(i);
st[0] = true;
cout << scc_cnt << endl;
for (int i = 1; i <= n; i ++ )
{
if (st[id[i]]) continue;
st[id[i]] = true;
sort(ans[id[i]].begin(), ans[id[i]].end());
for (int j = 0; j < ans[id[i]].size(); j ++ )
printf("%d ", ans[id[i]][j]);
puts("");
}
return 0;
}
by lichengyun @ 2022-10-07 22:07:13
@wusihao1931 Tarjan是O(N+M),M<<N^2……
by wusihao1931 @ 2022-10-08 09:07:00
@lichengyun 大哥看这步,假如只有一个联通块,那么外层循环(O(n)) + sort(O(nlogn)) 不就是O(n ^ 2logn)吗??
for (int i = 1; i <= n; i ++ )
{
if (st[id[i]]) continue;
st[id[i]] = true;
sort(ans[id[i]].begin(), ans[id[i]].end());
for (int j = 0; j < ans[id[i]].size(); j ++ )
printf("%d ", ans[id[i]][j]);
puts("");
}
by lichengyun @ 2022-10-11 21:35:41
@wusihao1931 时间复杂度是