只能看看题面，数据是错的。
就是求一张图的所有点双连通分量，将它们内部排序再外部排序数出来，关于点双连通分量没什么好讲的，网上各种博客都写烂了。还是直接上代码吧。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int MAXN=600000; int n; int Nt[MAXN<<1],to[MAXN<<1],Head[MAXN],tot; int root; int dfn[MAXN],low[MAXN],cut[MAXN]; vector<int>dcc[MAXN]; int num,cnt; int st[MAXN],top; void add(int a,int b){ Nt[++tot]=Head[a]; to[tot]=b; Head[a]=tot; } void tarjan(int x){ dfn[x]=low[x]=++num; st[++top]=x; if(x==root&&Head[x]==0){ dcc[++cnt].push_back(x); return; } int flag=0; for(int i=Head[x];i;i=Nt[i]){ int y=to[i]; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ flag++; if(x!=root||flag>1)cut[x]=1; cnt++; int z; do{ z=st[top--]; dcc[cnt].push_back(z); }while(z!=y); dcc[cnt].push_back(x); } } else low[x]=min(low[x],dfn[y]); } } bool cmp(vector<int>a,vector<int>b){ int lim=min(a.size(),b.size()); for(int i=0;i<lim;i++){ if(a[i]==b[i])continue; return a[i]<b[i]; } return a.size()<b.size(); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int x;scanf("%d",&x);x++; char str[7];scanf("%s",str); int num=0; for(int j=1;j<strlen(str);j++){ if(str[j]==')')break; num=num*10+str[j]^48; } for(int j=1;j<=num;j++){ int y;scanf("%d",&y);y++; add(x,y);add(y,x); } } for(int i=1;i<=n;i++){ if(!dfn[i])root=i,tarjan(i); } for(int i=1;i<=cnt;i++)sort(dcc[i].begin(),dcc[i].end()); sort(dcc+1,dcc+1+cnt,cmp); cout<<cnt<<endl; for(int i=1;i<=cnt;i++){ for(int j=0;j<dcc[i].size();j++){ printf("%d ",dcc[i][j]-1); } printf("\n"); } return 0; } |