社区讨论
过样例0分求调
B3609[图论与代数结构 701] 强连通分量参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m41b8of9
- 此快照首次捕获于
- 2024/11/28 20:48 去年
- 此快照最后确认于
- 2025/11/04 13:43 4 个月前
代码:
CPP#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
const int M = 1e5 + 10;
const int N = 1e4 + 10;
std::vector<int> graph[M];
std::vector<int> out_graph[N];
std::stack<int> st;
int n, m, p;
int dfn[M], low[M], cnt = 0;
int belong[N];
bitset<N> instack;
bitset<N> is_print;
void tarjan(int u, int fa)
{
cnt = cnt + 1;
dfn[u] = low[u] = cnt;
st.push(u);
instack[u] = true;
for(int n : graph[u])
{
if(n == fa)
{
fa = -1;
continue;
}
if(dfn[n] == 0)
{
tarjan(n, u);
low[u] = std::min(low[u], low[n]);
}
else if(instack[n])
{
low[u] = std::min(low[u], dfn[n]);
}
}
if(dfn[u] == low[u])
{
++p;
while(st.top() != u)
{
out_graph[p].push_back(st.top());
belong[st.top()] = p;
instack[st.top()] = false;
st.pop();
}
out_graph[p].push_back(u);
instack[st.top()] = false;
belong[st.top()] = p;
st.pop();
std::sort(out_graph[p].begin(), out_graph[p].end());
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int u, v, i = 1;i <= m;i ++)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
}
tarjan(1, -1);
printf("%d\n", p);
for(int i = 1;i <= n;i ++)
{
if(is_print[i]) continue;
for(int n : out_graph[belong[i]])
{
is_print[n] = true;
printf("%d ", n);
}
putchar('\n');
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...