洛谷P1726 上白泽慧音 强连通分量

给出 n ≤ 5 e 3 n\leq5e3 n≤5e3并且 m ≤ 5 e 4 m\leq5e4 m≤5e4的有向图，求最大强连通分量，对于大小相同的输出字典序最小的。

裸的tarjan缩点，复习一下tarjan求强连通分量：

从有向图某处开始 d f s dfs dfs，给每个点标记上一个时间戳 d f n i dfn_{i} dfni​。更新每个点到达的点的最小标号 l o w i low_{i} lowi​。

对于树边： l o w u = m i n ( l o w u , l o w v ) low_{u}=min(low_{u},low_{v}) lowu​=min(lowu​,lowv​)

对于返祖边： l o w u = m i n ( l o w u , d f n v ) low_{u}=min(low_{u},dfn_{v}) lowu​=min(lowu​,dfnv​)

然后回溯的时候对于所有的 d f n i = l o w i dfn_{i}=low_{i} dfni​=lowi​的点，取出栈中所有的点。显然这是一个强连通分量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=5e3+7;
vector<int> go[N]; 
int dfn[N],low[N],tim=0;
int s[N],top=0;
bool ins[N];
int id[N],scc=0; 
vector<int> bel[N]; 
void tarjan(int u) {
	dfn[u]=low[u]=++tim;
	s[++top]=u;
	ins[u]=1;
	for(auto &v:go[u]) {
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) {
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]) {
		id[u]=++scc;
		ins[u]=0;
		while(s[top]!=u) {
			id[s[top]]=scc;
			ins[s[top]]=0;
			top--;
		}
		top--;
	}
} 
bool cmp(vector<int> &a,vector<int> &b) {
	if(a.size()>b.size()) return 1;
	else if(a.size()==b.size()) {
		string A,B;
		for(auto &x:a) A+=x;
		for(auto &x:b) B+=x;
		return A<B; 
	}
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int opt,u,v;
		scanf("%d%d%d",&u,&v,&opt);
		if(opt==1) {
			go[u].push_back(v);
		}
		else {
			go[u].push_back(v);
			go[v].push_back(u);
		}
	}
	for(int i=1;i<=n;i++) {
		if(!dfn[i]) {
			tarjan(i); 
		}
	}
	for(int i=1;i<=n;i++) {
		bel[id[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) 
		sort(bel[i].begin(),bel[i].end());
	sort(bel+1,bel+1+n,cmp);
	printf("%d\n",bel[1].size());
	for(int i=0;i<bel[1].size();i++)
		printf("%d%c",bel[1][i],i+1==bel[1].size()?'\n':' ');  
	return 0;
}