传送门 https://www.luogu.org/problemnew/show/P1726
思路: 用 Tarjan 算出每个 scc, 并记录每个 scc 的大小, 找到最大的 scc->x, 最后从小到大枚举每个点, 看是否在 scc->x 中, 这样输出的方案一定是字典序最小的解.
- AC Code:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N=5000+100,M=50000+100;
- struct node{
- int to,nxt;
- }e[M];
- int head[N],tot;
- void add(int u,int v){
- e[++tot]=(node){v,head[u]};
- head[u]=tot;
- }
- int dfn[N],low[N],idx;
- int s[N],top;
- bool ins[N];
- int col[N],cnt,colv[N];
- int ans;
- void tarjan(int u){
- dfn[u]=low[u]=++idx;
- s[++top]=u;
- ins[u]=1;
- for(int i=head[u];i;i=e[i].nxt){
- int v=e[i].to;
- 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]){
- cnt++;
- while(s[top]!=u){
- col[s[top]]=cnt;
- ins[s[top]]=0;
- top--;
- colv[cnt]++;
- }
- col[u]=cnt;
- ins[u]=0;
- top--;
- colv[cnt]++;
- }
- ans=max(ans,colv[cnt]);
- }
- int main(){
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int a,b,t;
- scanf("%d%d%d",&a,&b,&t);
- add(a,b);
- if(t==2) add(b,a);
- }
- for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
- printf("%d\n",ans);
- int pos=0;
- for(int i=1;i<=n;i++){
- if(colv[col[i]]==ans){
- if(!pos) {
- pos=col[i];
- printf("%d",i);
- }
- else if(col[i]==pos) printf("%d",i);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2617790.html