求助 ,悬赏关注
查看原帖
求助 ,悬赏关注
711584
Lienqwq楼主2022/10/8 21:10

调了很久,样例一直输出:

0

1 2 3 4 5

#include<bits/stdc++.h>
using namespace std;

const int _ = 5005;
int n ,m ,a[_] ,dfn[_] ,low[_] ,ts ,stk[_] ,head[_] ,scc_cnt ,id[_] ,all[_] ,ans ,top ,cnt ,num[_];
struct Edge
{
	int to ,nxt;
}e[_ * 10];

inline void add(int x ,int y)
{
	e[++cnt].nxt = head[x];
    e[cnt].to = y;
	head[x] = cnt;
}

inline void tarjan(int u)
{
	dfn[u] = low[u] = ++ts;
	stk[++top] = u;
	for(int i = head[u];i;i = e[i].nxt) 
	{
		int j = e[i].to;
		if(!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u] ,low[j]);
		}
		else if(!id[j])
			low[u] = min(low[u] ,dfn[j]);
	}
	if(dfn[u] == low[u])
	{
		int y;
		id[u] = ++scc_cnt;
        ++all[scc_cnt];
        while(y != u)
		{
			id[stk[top--]] = scc_cnt;
            ++all[scc_cnt];
		}
        top--;
	}
}

int main()
{
	scanf("%d%d" ,&n ,&m);
	for(int i = 1;i <= m;++i)
	{
		int x ,y ,z;
		scanf("%d%d%d" ,&x ,&y ,&z);
		if(z == 1) add(x ,y);
		else 
		{
			add(x ,y);
			add(y ,x);
		}
	}
	for(int i = 1;i <= n;++i)
        if(!dfn) tarjan(i);
	for(int i = 1;i <= scc_cnt;++i)
		ans = max(ans ,all[i]);
	printf("%d\n" ,ans);
    
	for(int i = 1;i <= n;++i)
		if(all[id[i]] == ans) printf("%d " ,i);
	return 0;
}
2022/10/8 21:10
加载中...