[洛谷P1726][codevs1332]上白泽慧音

题目大意：求一个有向图的最大强连通分量中点的个数，并输出这些点（字典序最小）。

解题思路：裸的强连通分量。

数据小，求完强连通分量后排序+vector大小比较即可（vector有小于运算符）。

C++ Code：

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cstdarg>

#include<stack>

#include<vector>

#include<algorithm>

using std::sort;

int n,m,cnt,head[5050],low[5050],dfn[5050],ltfl,idx=0;

std::stack<int>s;

bool vis[5050];

struct edge{

	int to,nxt;

}e[50505];

std::vector<int>v[5050];

inline int min(int a,int b){return a<b?a:b;}

inline int max(int a,int b){return a>b?a:b;}

inline int readint(){

	char c=getchar();

	for(;!isdigit(c);c=getchar());

	int d=0;

	for(;isdigit(c);c=getchar())

	d=(d<<3)+(d<<1)+(c^'0');

	return d;

}

inline void read(int cnt,...){

	va_list arg_ptr;

	va_start(arg_ptr,cnt);

	for(int i=0;i<cnt;++i){

		int* p=va_arg(arg_ptr,int*);

		*p=readint();

	}

}

void tarjan(int now){

	vis[now]=true;

	s.push(now);

	dfn[now]=low[now]=++idx;

	for(int i=head[now];i;i=e[i].nxt)

	if(!dfn[e[i].to]){

		tarjan(e[i].to);

		low[now]=min(low[now],low[e[i].to]);

	}else

	if(vis[e[i].to])low[now]=min(low[now],dfn[e[i].to]);

	if(low[now]==dfn[now]){

		++ltfl;

		int k;

		do{

			k=s.top();

			s.pop();

			vis[k]=false;

			v[ltfl].push_back(k);

		}while(k!=now);

	}

}

int main(){

	cnt=ltfl=0;

	memset(head,0,sizeof head);

	read(2,&n,&m);

	while(m--){

		int u,v,t;

		read(3,&u,&v,&t);

		e[++cnt]=(edge){v,head[u]};

		head[u]=cnt;

		if(t-1){

			e[++cnt]=(edge){u,head[v]};

			head[v]=cnt;

		}

	}

	memset(low,0,sizeof low);

	memset(dfn,0,sizeof dfn);

	memset(vis,0,sizeof vis);

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

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

	int p=0;

	std::vector<int>ans;

	bool hasans=false;

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

	p=max(p,v[i].size());

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

	if(v[i].size()==p){

		sort(v[i].begin(),v[i].end());

		if(!hasans){

			hasans=true;

			ans=v[i];

		}else

		if(v[i]<ans)ans=v[i];

	}

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

	--p;

	for(int i=0;i<p;++i)printf("%d ",ans[i]);

	printf("%d\n",ans[p]);

	return 0;

}