Zi_Gao @ 2023-07-30 09:16:37
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}
struct EDGE{
int v,id;
};
std::vector<EDGE> e[500010];
std::vector<int> edcc[500010];
std::stack<int> stack;
int dfn[500010],low[500010],cnt,tot;
char isEdcc[2000010],vis[500010];
void addEdge(int u,int v,int id){
e[u].push_back(EDGE{v,id});
return;
}
void tarjan(int u,int p){
// print(u);putchar(' ');
low[u]=dfn[u]=(dfn[p]+1);
stack.push(u);
for(auto edge:e[u])
if(edge.v!=p){
if(dfn[edge.v]&&edge.v!=p) low[u]=std::min(low[u],dfn[edge.v]);
else{
tarjan(edge.v,u);
if(low[edge.v]>dfn[u]) isEdcc[edge.id]=1;
low[u]=std::min(low[u],low[edge.v]);
}
}
return;
}
void dfs(int u){
vis[u]=1;
edcc[cnt].push_back(u);
for(auto edge:e[u])
if(!vis[edge.v]&&!isEdcc[edge.id])
dfs(edge.v);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("name.in", "r", stdin);
freopen("name.out", "w", stdout);
#endif
register int i,u,v;
int n=read();
int m=read();
for(i=0;i<m;++i){
u=read();
v=read();
if(u==v) continue;
addEdge(u,v,i);
addEdge(v,u,i);
}
for(i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,i);
for(i=1;i<=n;++i)
if(!vis[i]){
dfs(i);
++cnt;
}
print(cnt);putchar('\n');
for(i=0;i<cnt;++i){
print(edcc[i].size());putchar(' ');
for(auto u:edcc[i]){
print(u);putchar(' ');
}
putchar('\n');
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
这份代码中并没有记录来时的边,只传入了父亲,但是还是可以跑对,不知道有没有可以卡的方法。
by Nuclear_Pasta @ 2023-07-30 09:22:48
@Zi_Gao
input:
3 3
1 2
2 1
1 3
output:
2
2 1 2
1 3
by Zi_Gao @ 2023-07-30 09:25:25
@departure2020 似乎并没有卡掉
by Nuclear_Pasta @ 2023-07-30 09:32:44
@Zi_Gao
input:
4 5
1 2
2 3
3 2
3 4
1 4
output:
3
1 1
2 2 3
1 4
by Zi_Gao @ 2023-07-30 09:36:56
@departure2020 您给出的output正确吗?我拿题解跑是
1
4 1 4 3 2
和我的一样
by Nuclear_Pasta @ 2023-07-30 09:40:45
@Zi_Gao 抱歉,output错了,重新出一个。
input:
4 4
1 2
2 3
3 2
3 4
output:
3
1 1
2 2 3
1 4
by Zi_Gao @ 2023-07-30 09:44:16
@departure2020 很遗憾并没有卡掉
by zzk2010 @ 2023-07-31 10:03:50
@Zi_Gao 看看这个
个人认为传父亲也是可以的。题解区代码大多用的是链式前向星,所以记录边更方便。两者本质都是为了不走回头路吧。
by Zi_Gao @ 2023-07-31 10:56:17
@zzk2010 ok