上白泽慧音

洛咕

题意:给定一个\(n(n<=5000)\)个点\(m(m<=50000)\)条边的图,边可能是单向边也可能是双向边,求最大的强连通分量所包含的点数,并且输出从小到大点的序号.如果有多个方案,输出包含的点的字典序最小的那个强连通分量.

分析:既然题目都翻译到这个份上了,肯定就是tarjan的模板题了.记录一下每个强连通分量的size就好.

感觉代码长度都用在判断是不是有多种方案以及输出方案上了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=5005;
const int M=100005;
int n,m,maxn,id,ans;
int tot,head[N],to[M],nxt[M];
int top,sum,timeclock;
int size[N],dfn[N],low[N],st[N],color[N];
vector<int>q;
inline void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++timeclock;
    st[++top]=u;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!color[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        color[u]=++sum;
        ++size[sum];
        while(st[top]!=u){
            color[st[top]]=sum;
            ++size[sum];
            --top;
        }
        --top;
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),opt=read();
        if(opt==1)add(a,b);
        else add(a,b),add(b,a);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=sum;++i){
        maxn=max(maxn,size[i]);
    }
    for(int i=1;i<=sum;++i){
        if(size[i]==maxn)q.push_back(i);
    }
    if(q.size()==1){
        id=q.front();
        for(int i=1;i<=n;++i)
            if(color[i]==id)++ans;
        printf("%d\n",ans);
        for(int i=1;i<=n;++i)
            if(color[i]==id)printf("%d ",i);
        printf("\n");return 0;
    }
    for(int i=1;i<=n;++i){
        int nn=q.size();
        for(int j=0;j<nn;++j)
            if(color[i]==q[j])id=q[j];
    }
    for(int i=1;i<=n;++i)if(color[i]==id)++ans;
    printf("%d\n",ans);
    for(int i=1;i<=n;++i)if(color[i]==id)printf("%d ",i);
    printf("\n");
    return 0;
}

上白泽慧音

原文：https://www.cnblogs.com/PPXppx/p/11383416.html