【luogu P1726 上白泽慧音】题解

题目链接：https://www.luogu.org/problemnew/show/P1726

菜

#include <stack>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 50000 + 10;

int n, m, root;

struct edge{

	int from, to, next;

}e[maxn<<2];

int head[maxn], cnt;

int dfn[maxn], low[maxn], color[maxn], tim, num, tong[maxn];

bool vis[maxn];

stack<int> s;

void add(int u, int v)

{

	e[++cnt].from = u;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

void tarjan(int x)

{

	dfn[x] = low[x] = ++tim;

	s.push(x); vis[x] = 1;

	for(int i = head[x]; i != -1; i = e[i].next)

	{

		int v = e[i].to;

		if(!dfn[v])

		{

			tarjan(v);

			low[x] = min(low[x], low[v]);

		}

		else if(vis[v])

		{

			low[x] = min(low[x], low[v]);

		}

	}

	if(dfn[x] == low[x])

	{

		color[x] = ++num;

		vis[x] = 0;

		while(s.top() != x)

		{

			color[s.top()] = num;

			vis[s.top()] = 0;

			s.pop();

		}

		s.pop();

	}

}

int main()

{

	memset(head, -1, sizeof(head));

	scanf("%d%d",&n,&m);

	for(int i = 1; i <= m; i++)

	{

		int u, v, w;

		scanf("%d%d%d",&v,&u,&w);

		if(w == 1)

		{

			add(u, v);

		}

		else

		{

			add(u, v), add(v, u);

		}

	}

	for(int i = 1; i <= n; i++)

		if(!dfn[i]) tarjan(i);

	for(int i = 1; i <= n; i++)

		tong[color[i]]++;

	int ans = -1, flag;

	for(int i = 1; i <= num; i++)

	{

		if(ans < tong[i])

		{

			ans = tong[i];

			flag = i;

		}

	}

	printf("%d\n",ans);

	for(int i = 1; i <= n; i++)

		if(color[i] == flag) printf("%d ",i);

	return 0;

}

巴特西

【luogu P1726 上白泽慧音】题解

最新文章

热门文章

巴特西

【luogu P1726 上白泽慧音】 题解

最新文章

热门文章

【luogu P1726 上白泽慧音】题解