思路：
Tarjan求出所有的连通分量，然后$O(n)$计算每个连通分量的大小，再$O(n)$找出字典序最小的。
1 #include<stack> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int V=5001; 13 std::vector<int> e[V]; 14 inline void add_edge(const int u,const int v) { 15 e[u].push_back(v); 16 } 17 int dfn[V]={0},low[V]={0},scc[V]={0},cnt=0,id=0; 18 bool ins[V]={0}; 19 std::stack<int> s; 20 void Tarjan(const int x) { 21 dfn[x]=low[x]=++cnt; 22 s.push(x); 23 ins[x]=true; 24 for(unsigned i=0;i<e[x].size();i++) { 25 int &y=e[x][i]; 26 if(!dfn[y]) { 27 Tarjan(y); 28 low[x]=std::min(low[x],low[y]); 29 } 30 else if(ins[y]) { 31 low[x]=std::min(low[x],dfn[y]); 32 } 33 } 34 if(dfn[x]==low[x]) { 35 id++; 36 int y; 37 do { 38 y=s.top(); 39 s.pop(); 40 scc[y]=id; 41 ins[y]=false; 42 } while(x!=y); 43 } 44 } 45 int size[V]; 46 int main() { 47 int n=getint(); 48 for(int m=getint();m;m--) { 49 int u=getint(),v=getint(),t=getint(); 50 if(t==1) { 51 add_edge(u,v); 52 } 53 else { 54 add_edge(u,v); 55 add_edge(v,u); 56 } 57 } 58 for(int i=1;i<=n;i++) { 59 if(!dfn[i]) Tarjan(i); 60 } 61 int maxsize=0; 62 for(int i=1;i<=n;i++) { 63 size[scc[i]]++; 64 maxsize=std::max(maxsize,size[scc[i]]); 65 } 66 printf("%d ",maxsize); 67 int sccid; 68 for(int i=1;i<=n;i++) { 69 if(size[scc[i]]==maxsize) { 70 sccid=scc[i]; 71 break; 72 } 73 } 74 for(int i=1;i<=n;i++) { 75 if(scc[i]==sccid) printf("%d ",i); 76 } 77 return 0; 78 }