记录编号	152202	评测结果	AAAAAAAAAA
题目名称	[東方S1] 上白泽慧音	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-03-13 19:46:08	内存使用	0.49 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <string>
#include <deque>
#include <map>
#include <list>
#include <stack>
using namespace std;
int n,m,low[5001],l[5001],t=0,w=0,dfn[5001]={0},ans=0,maozhuxi=9999999,k=0;
vector<int>f[5001],scc[5001];
	ifstream in("classroom.in");
	ofstream out("classroom.out");
stack<int> s;
void tarjan(int u) {
    dfn[u] = low[u] = ++t;
    l[u] = 1;
    s.push(u);
    for(int i=0; i<f[u].size(); i++) 
	{
        int v = f[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(l[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
	{
        w++;
		int v;
        do 
		{
            l[v = s.top()] = 0;
			scc[w].push_back(v);
            s.pop();
        } while(u != v);
    }
}
int main()
{
	int i,j,x1,x2,x3;

	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>x1>>x2>>x3;
		if(x3==2)
		{
			f[x1].push_back(x2);
			f[x2].push_back(x1);
		}
		else
		{
			f[x1].push_back(x2);
		}
	}
	for(i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i);
	}
	/*for(i=1;i<=n;i++)
	{
		out<<i<<' '<<':';
		for(j=0;j<f[i].size();j++)
		{
			out<<f[i][j]<<' ';
		}
		out<<endl;
	}*/
	
	for(i=1;i<=w;i++)
	{
		int q=scc[i].size();
		if(q>ans)ans=q;
		sort(scc[i].begin(),scc[i].end());
	}
	/*for(i=1;i<=w;i++)
	{
		for(j=0;j<scc[i].size();j++)
		{
			out<<scc[i][j]<<' ';
		}
		out<<endl;
	}*/
	for(i=1;i<=w;i++)
	{
		if(scc[i].size()==ans)
		{
			if(scc[i][0]<maozhuxi)
			{
				maozhuxi=scc[i][0];
				k=i;
			}
		}
	}
	out<<ans<<endl;
	for(i=0;i<scc[k].size();i++)out<<scc[k][i]<<' ';
	in.close();
	out.close();
	return 0;
}