记录编号	190133	评测结果	AAAAAAAAAA
题目名称	[東方S1] 上白泽慧音	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2015-10-02 16:22:19	内存使用	1.40 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
const int maxn=10000+100;
stack<int>s;
struct edge{
	int to,next;
}G[maxn*10];
int h[maxn],dfn[maxn],low[maxn],num=0;
int cnt[maxn],Index=0,id[maxn],tot=0,n,m;
bool instack[maxn];
vector<int>p[maxn];

void add(int x,int y){
	++tot; G[tot].to=y;
	G[tot].next=h[x]; h[x]=tot;
}

void tarjan(int x){
	dfn[x]=low[x]=++Index;
	s.push(x); instack[x]=1;
	for (int i=h[x];i;i=G[i].next)
	   if (!dfn[G[i].to]){
		  tarjan(G[i].to);
		  if (low[G[i].to]<low[x])
			 low[x]=low[G[i].to];
	   }
	   else if (instack[G[i].to]&&dfn[G[i].to]<low[x])
		  low[x]=dfn[G[i].to];
	if (dfn[x]==low[x]){
		num++; int k;
		do{
			k=s.top(); s.pop();
			instack[k]=0;
			id[k]=num; cnt[num]++;
			p[num].push_back(k);
		}while (k!=x);
	}
}

int main()
{
	freopen("classroom.in","r",stdin);
	freopen("classroom.out","w",stdout);
	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);}
	}
	memset(dfn,0,sizeof(dfn));
	memset(id,-1,sizeof(id));
	for (int i=1;i<=n;++i)//求分量
	   if (!dfn[i])
		  tarjan(i);
	vector<int>v; int maxx=0;
	for (int i=1;i<=num;++i)//处理最大分量
	   if (cnt[i]>maxx){
			maxx=cnt[i];
			v.clear(); v.push_back(i);
	   }
	   else if (cnt[i]==maxx) v.push_back(i);
	priority_queue<int>Q;//处理字典序
	for (int i=0;i<v.size();++i){
		int minn=0x7fffffff/3;
		for (int j=0;j<p[v[i]].size();++j)//比较谁的字典序更小
		   if (p[v[i]][j]<minn) minn=p[v[i]][j];
		if (!Q.empty()){//更新
			int k=-Q.top();
			if (k>minn){
				while (!Q.empty()) Q.pop();//清空
				for (int j=0;j<p[v[i]].size();++j)
				   Q.push(-p[v[i]][j]);
			}
		}
		else
           for (int j=0;j<p[v[i]].size();++j)
		      Q.push(-p[v[i]][j]);
	}
	printf("%d\n",maxx);
	while (!Q.empty()){
		int k=-Q.top();
		printf("%d ",k);
		Q.pop();
	}
	return 0;
}