【洛谷P1726】上白泽慧音

上白泽慧音

题目链接

强联通分量模板题，Tarjan求强联通分量，记录大小即可

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 5010
#define M 100010
int n,m,Head[N],Enum,stack[N],top,ms;
int dfn[N],cnt,low[N],belong[N],size[N],num;
bool ins[N];
struct NODE{
    int to,next;
} e[M];
inline void add(int x,int y){
    e[++Enum].to=y;
    e[Enum].next=Head[x];
    Head[x]=Enum;
}
inline int read(){
    int x=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
    return x;
}
inline void Tarjan(int u){
    dfn[u]=low[u]=++cnt;
    ins[u]=1; stack[++top]=u;
    for(int i=Head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=std::min(low[u],low[v]);
        }
        else if(ins[v])
            low[u]=std::min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        belong[u]=++num;
        while(stack[top]!=u){
            int k=stack[top];
            belong[k]=num;
            size[num]++;
            ins[k]=0;
            top--;
        } size[num]++;
        top--; ins[u]=0;
    }
}
int main()
{
    n=read(); m=read();
    int x,y,t;
    for(int i=1;i<=m;i++){
        x=read(); y=read(); t=read();
        add(x,y); if(t==2) add(y,x);
    }
    for(int i=1;i<=n;i++)
     if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=num;i++)
     if(size[i]>ms) ms=size[i];
    int ans;
    for(int i=1;i<=n;i++)
     if(size[belong[i]]==ms){
         ans=belong[i];
         break;
     }
    printf("%d
",ms);
    for(int i=1;i<=n;i++)
     if(belong[i]==ans)
      printf("%d ",i);
    puts("");
    return 0;
}