社区讨论

过样例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 条回复,欢迎继续交流。

正在加载回复...