luogu——————
解法： 一个绝对连通区域就是一个强连通分量 因为题目要求输出最大强连通分量的规模，所以不需要考虑重边的问题（即会出现大包小的情况），如果要输出教学区的个数，则需要减去此种情况
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> using namespace std; int num[2*50009],head[5009],nxt[2*50009],fig[5009],mc=-1,cnt=0; int n,m,dfs_num=0,dfn[5009],low[5009],color_num=0,color[5009],st[5009],kk; bool vis[5009]; int top=0; void Tarjan(int x) { dfn[x]=++dfs_num; low[x]=dfs_num; vis[x]=true; st[++top]=x; for(int i=head[x];i;i=nxt[i]) { int k=num[i]; if(!dfn[k]) { Tarjan(k); low[x]=min(low[x],low[k]); } else if(vis[k]) low[x]=min(dfn[k],low[x]); } if(low[x]==dfn[x]) { vis[x]=false; color[x]=++color_num; int t=1; while(st[top]!=x) { vis[st[top]]=false; color[st[top]]=color_num; top--;t++; } top--; fig[color_num]=t; if(t>mc){//记录点最多的强连通分量里点的个数 mc=t; kk=color_num;//记录点最多的强连通分量的代号 } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,t; scanf("%d%d%d",&a,&b,&t); cnt++; num[cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; if(t==2) { cnt++; num[cnt]=a; nxt[cnt]=head[b]; head[b]=cnt; } } for(int i=1;i<=n;i++) { if(!dfn[i]) Tarjan(i); } printf("%d\n",mc);// for(int i=1;i<=n;i++) { if(color[i]==kk)//输出强连通分量里的点 printf("%d ",i); } return 0; }