【洛谷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=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
inline void Tarjan(int u){
dfn[u]=low[u]=++cnt;
ins[u]=; 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]=;
top--;
} size[num]++;
top--; ins[u]=;
}
}
int main()
{
n=read(); m=read();
int x,y,t;
for(int i=;i<=m;i++){
x=read(); y=read(); t=read();
add(x,y); if(t==) add(y,x);
}
for(int i=;i<=n;i++)
if(!dfn[i]) Tarjan(i);
for(int i=;i<=num;i++)
if(size[i]>ms) ms=size[i];
int ans;
for(int i=;i<=n;i++)
if(size[belong[i]]==ms){
ans=belong[i];
break;
}
printf("%d\n",ms);
for(int i=;i<=n;i++)
if(belong[i]==ans)
printf("%d ",i);
puts("");
return ;
}
上一篇:HDOJ-1003 Max Sum(最大连续子段 动态规划)


下一篇:Android APK反编译就这么简单 详解(附图)--转