原题链接
直到今天 我才知道 幻想乡还有这么一位 看起来很可爱的 老师
普通的寻找强连通分量 普通的统计最大 普通的输出 除了我背错板子了以外 一切都是那么完美
今天的幻想乡 也是和平的一天呢
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> using namespace std; int n,m,a,b,t,dfn[5000+5],low[5000+5],vis[5000+5],top,tot,dfni,st[5000+5],love,pop,popclo; int sum[5000+5],num[50000+5],head[5000+5],nxt[50000+5],clor[10000+5],clo; void tarjan(int x) { int i; dfni++; dfn[x]=dfni; low[x]=dfni; vis[x]=1; top++; st[top]=x; for(i=head[x];i;i=nxt[i]) { if(!dfn[num[i]]) { tarjan(num[i]); low[x]=min(low[x],low[num[i]]); } else if(vis[num[i]]) low[x]=min(low[x],low[num[i]]); } if(low[x]==dfn[x]) { vis[x]=0; clo++; clor[x]=clo; love=1; while(st[top]!=x) { love++; clor[st[top]]=clo; vis[st[top]]=0; top--; } if(love>pop) { pop=love; popclo=clo; } top--; } } void add(int p1,int p2) { tot++; num[tot]=p2; nxt[tot]=head[p1]; head[p1]=tot; } int main() { int i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&t); if(t==1) add(a,b); if(t==2) { add(a,b); add(b,a); } } for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i); printf("%d\n",pop); for(i=1;i<=n;i++) if(clor[i]==popclo) printf("%d ",i); return 0; }