apple_vinegar @ 2024-08-12 11:44:08
甚至下载的测试点也是秒过 输入 4 3 1 2 4 2 2 2 输出 4 1 1 1 2 1 3 1 4
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=5e5+5;
int e[N],ne[N],h[N],idx=2,dfn[M],low[M],cnt,vis[M],num,n,m;
bool bz[N*2];
vector <int>ans[N*2];
int add(int a,int b){
e[idx] =b;
ne[idx]=h[a];
h[a]=idx++;
}
void tarjan(int u,int fa){
dfn[u]=low[u]=++cnt;
for(int i=h[u];i;i=ne[i]){
int v=e[i];
if(dfn[v]==0){
tarjan(v,i);
if(dfn[u]<low[v]) bz[i]=bz[i^1]=1;
low[u]=min(low[u],low[v]);
}
else if(i!=(fa^1)){
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int u,int id){
vis[u]=id,ans[id-1].push_back(u);
for(int i=h[u];i;i=ne[i]){
int v=e[i];
if(vis[v] || bz[i])continue;
dfs(v,id);
}
}
int read(){
int a=1,b=0;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-'){
a=-a;ch=getchar();
}
}
while(ch>='0' && ch<='9'){
b=(b<<1)+(b<<3)+(ch^48);
ch=getchar();
}
return b;
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u,v;
u=read(),v=read();
if(u==v) continue;
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,0);
}
// for(int i=1;i<=n;i++)cout<<dfn[i]<<" "<<low[i]<<endl;
for(int i=1;i<=n;i++){
if(vis[i]==0){
dfs(i,++num);
}
}
printf("%d\n",num);
for(int i=0;i<num;i++){
printf("%d",ans[i].size());
for(int j=0;j<ans[i].size();j++) printf(" %d",ans[i][j]);
printf("\n");
}
return 0;
}
by yx666 @ 2024-08-12 11:47:24
@penggc16801 add
没返回值
by apple_vinegar @ 2024-08-12 11:50:44
@yx666 多谢,但是为什么快读会T啊
by yx666 @ 2024-08-12 11:59:15
@penggc16801 快读打错了
要把第一个 while
改成
while(ch<'0' || ch>'9'){
if(ch=='-')
a=-a;
ch=getchar();
}